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.

Improve this question
$\endgroup$
6
  • $\begingroup$ I've just found Lowest Common Ancestor, e.g. here. But this seems to work only on pairs. $\endgroup$
    – Sebastian
    Commented Dec 1, 2013 at 18:10
  • $\begingroup$ How is this different from simply going through vertices from root to "leaves" and grouping their children? $\endgroup$
    – arsaKasra
    Commented Dec 1, 2013 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
    Commented Dec 1, 2013 at 20:58
  • $\begingroup$ So, you are talking about latices? $\endgroup$
    – Jens Piegsa
    Commented Dec 7, 2013 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
    Commented Dec 7, 2013 at 14:39

3 Answers 3

Reset to default
1
$\begingroup$

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

Improve this answer
$\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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ I used Dijkstra only to determine the layers. This is separated from the problem of grouping. $\endgroup$
    – Sebastian
    Commented Dec 7, 2013 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
    Commented Dec 7, 2013 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
    Commented Dec 7, 2013 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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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