4
$\begingroup$

Given is the following graph which is logically divided into layers (with Dijkstra's shortest paths algorithm):

 Vertices   Layer

    Root      0
   /   \
  A     B     1
 / \    |
C   D   E     2
 \  |  /
  \ | /
    F         3

Now I'm looking for an algorithm which groups vertices when they have a (single) common ancestor in the previous layer, e.g. for the graph in the example the groups would be:

0: A, B
1: C, D
2: E
3: F

I know that this is doable by visiting vertices and comparing ancestors but I was wondering whether there is a well known algorithm for it.

Update: My question is really only related to find groups. I'm aware of the fact, that I can traverse vertices and test for incoming edges and group those vertices. Furthermore, the graph is fully constructed.

One (now deleted) answer mentioned DFS, which creates a search forest (as BFS creates a search tree which I basically used for levels, though I mentioned Dijkstra). So, I assume that combining BFS and DFS could give me the desired result.

$\endgroup$
  • $\begingroup$ I've just found Lowest Common Ancestor, e.g. here. But this seems to work only on pairs. $\endgroup$ – Sebastian Dressler Dec 1 '13 at 18:10
  • $\begingroup$ How is this different from simply going through vertices from root to "leaves" and grouping their children? $\endgroup$ – arsaKasra Dec 1 '13 at 19:23
  • $\begingroup$ There is no difference. I just asked for the name of an algorithm, if there is any common known. $\endgroup$ – Sebastian Dressler Dec 1 '13 at 20:58
  • $\begingroup$ So, you are talking about latices? $\endgroup$ – Jens Piegsa Dec 7 '13 at 12:16
  • $\begingroup$ @JensPiegsa I'm unsure whether my stated problem always fulfills the criterions of a lattice, maybe I should prove this somehow? $\endgroup$ – Sebastian Dressler Dec 7 '13 at 14:39
1
$\begingroup$

this seems to be known as the "Lowest Common Ancestor" problem of graphs. see eg

$\endgroup$
0
$\begingroup$

Maybe you can use A* algorithm as a better alternative to dijkstra and use the metric function ( heuristic ) of a* to group or flag your vertices in an appropriate way.

Change due to assessment.

I think there is no appropriate algorithm doin that. Because you need to span the whole graph before knowing which connections are established. With the metric or heuristic approach you can predict some kind of grouping during the evolvement of the graph by defining rules for grouping within your metric function.

Best regards.

$\endgroup$
  • $\begingroup$ I used Dijkstra only to determine the layers. This is separated from the problem of grouping. $\endgroup$ – Sebastian Dressler Dec 7 '13 at 14:44
  • $\begingroup$ Yeah i know. I thought you wanted to realize grouping during the evolvement of the graph. If not i don't understand your question because after the creation of the graph you have all information you need to group by simply traverse the every node of every layer. Please concrete your question. $\endgroup$ – Christian Schack Dec 7 '13 at 17:08
  • 1
    $\begingroup$ Thanks for clarification, I updated the question to get things clearer a bit. Also thanks for mentioning A* which is of great interest for this problem w/r/t a varied scenario, i.e. a not fully constructed graph. $\endgroup$ – Sebastian Dressler Dec 7 '13 at 20:41
0
$\begingroup$

I think Breath First Search would work, (by searching for a node not in the graph so, I guess check for a NIL node) and just print out the adjacent edges, when marking them as searched. It will search all the nodes until there are no nodes left to search and NIL is found.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.