Combining Graphs: Finding Solutions through Graph Homorphisms

Join the discussion
Ask a follow-up here, or get your own question answered by working scientists, mathematicians and engineers — people, not an autocomplete.
Real named experts · corrections over time · the nuance an AI answer skips
Sign up Log in
6 replies · 1K views
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
 
Physics 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!