Combining Graphs: Finding Solutions through Graph Homorphisms

Click For Summary

Discussion Overview

The discussion centers around the challenge of combining separate graphs into a single graph for an architectural project. Participants explore methods for generating graph homomorphisms and the implications of graph representation in the context of house design.

Discussion Character

  • Exploratory
  • Technical explanation
  • Conceptual clarification
  • Debate/contested

Main Points Raised

  • One participant describes their project involving the combination of graphs representing different activities and attributes related to house design, using methods like maximum graph homomorphism and an exact algorithm.
  • Another participant questions the clarity of the graph representations, suggesting that nodes should represent specific activities rather than a mix of actions, nouns, and attributes.
  • A later reply emphasizes the need for a clearer definition of what each graph represents to facilitate better merging of the graphs.
  • One participant asserts that merging graphs can be straightforward by forming a new graph from the union of nodes and replicating edges, while also noting the importance of eliminating duplicate nodes.
  • Another participant suggests methods for combining weights of edges in the merged graph, proposing options like simple sums or more complex functions like sum of squares or square roots.

Areas of Agreement / Disagreement

Participants express differing views on the complexity of merging graphs, with some suggesting it is straightforward while others emphasize the need for careful consideration of graph definitions and representations. The discussion remains unresolved regarding the best approach to merging the graphs effectively.

Contextual Notes

Participants highlight limitations in the current graph definitions and the potential for confusion in representing activities and attributes. There is also mention of the need to clarify how to combine weights in the merged graph.

Who May Find This Useful

This discussion may be of interest to those involved in architectural design, graph theory, or anyone looking to understand the complexities of graph merging and representation in project planning.

seel
Messages
4
Reaction score
0
TL;DR
We are trying to find a way to combine individual graphs into one.
We are working on an architectural project using graphs and we are looking for a way to combine separate graphs into one. We looked into methods to generate graph homorphisms, following the maximum graph homomorphism (MGH) (Langberg et al. 2006) and Paweł Rzążewski’s Exact Algorithm (2014), which maps adjacent vertices in separate graphs. We are using an undirected weighted graph (as we need to establish weights of the links bt nodes). Any help with this project would be great!

homorphism.png
 
Technology news on Phys.org
Can you be more specific about the goal? What are the graphs meant to represent?
 
seel said:
Summary:: We are trying to find a way to combine individual graphs into one.

We are working on an architectural project using graphs and we are looking for a way to combine separate graphs into one. We looked into methods to generate graph homorphisms, following the maximum graph homomorphism (MGH) (Langberg et al. 2006) and Paweł Rzążewski’s Exact Algorithm (2014), which maps adjacent vertices in separate graphs. We are using an undirected weighted graph (as we need to establish weights of the links bt nodes). Any help with this project would be great!

View attachment 275331
Your graphs seem weird to me and possibly not well-thought out. For example, the socializing graph contains actions (talking, meeting, drinking) mixed in with nouns (TV, fireplace, music), and adjectives/adverbs(loud, low-light, by-the-courtyard). The cooking graph has similar problems.

A better idea, IMO, would be to decide what each graph should represent, and each node should be some aspect of what the graph is about. For the socializing graph-- is it activities? If so, then each node in the graph should represent some activity. This would exclude "low light" and "loud" which are not activities, as well as "by-the-courtyard."

When you define the graphs better, maybe combining the graphs would produce something more sensible.
 
  • Like
Likes   Reactions: seel
Hi @Mark44, many thanks for your comments. The activities/attributes in the graphs I posted are just an example. I am more interested in finding a good way to merge two or more graphs into one. If you have any idea, it would be helpful! thanks!
 
Jarvis323 said:
Can you be more specific about the goal? What are the graphs meant to represent?
we are breaking down usual programatic organisations in house design (living room, bedrooms, kitchen etc.) into activities (eating, slepping, socialising, cooking, storing, playing music etc.). Each of this activity has a number of attributes (silent, private, loud etc.) linked to it with certain weights.
We modeled this by using 1 graph per activity (sleeping etc.) linked to several attributes (loud, private etc.). We are looking for a way to merge all graphs into one (evaluating the wieghts and proximities) to obtain a new spatial configuration for the entire house. I hope it clarifies a bit.
 
The algorithms you refer to are not necessary for this problem: merging graphs is easy.

  1. Form a new graph from the union of the nodes in the graphs to be merged. Note that elements of a set are unique so you need to eliminate duplicates (in the example this has been done correctly for e.g. 'loud' but not for 'by the courtyard').
  2. Replicate each edge in each graph to be merged in the new graph (this appears to have been done correctly in the example from a quick inspection).

From your last post, the next stage will be to eliminate the 'attribute' nodes from the merged graph so that 'activities' are linked by edges; you will need to determine a function for combining the weights: this could be a simple sum, or you could investigate the sum of squares (which will favour strong connections) or square roots (which will boost weak connections).
 
  • Like
Likes   Reactions: seel
@pbuk great! Many thanks. Will work on it and post back here. Thanks!
 

Similar threads

  • · Replies 7 ·
Replies
7
Views
4K
  • · Replies 2 ·
Replies
2
Views
4K
Replies
24
Views
8K
  • · Replies 13 ·
Replies
13
Views
4K
  • · Replies 1 ·
Replies
1
Views
3K
  • · Replies 1 ·
Replies
1
Views
4K
  • · Replies 5 ·
Replies
5
Views
3K
  • · Replies 1 ·
Replies
1
Views
3K
  • · Replies 1 ·
Replies
1
Views
4K
  • · Replies 1 ·
Replies
1
Views
4K