0
$\begingroup$

I have the following multi-edge, undirected graph.

graph

I would like to extract the following tree from it, if I start from the node $A$.

tree

Do you know of any algorithm that I can use to achieve that ?


The problem I am trying to solve is the following.

The first graph represent different relational tables I want to join. Each edge $e_i$ represents one join between two tables (two tables could be joined on different fields, for example).

From that graph, I need to create the tree depicted in the second figure. That tree is then used for executing the joins.

Thanks

$\endgroup$
  • 2
    $\begingroup$ Welcome to CS.SE! Can you specify your problem in general? One example is not a replacement for a specification of the task. Thanks. $\endgroup$ – D.W. Sep 2 '16 at 14:42
  • 4
    $\begingroup$ Thanks for the attempt, but I'm afraid that's not what I was asking for. I want a problem specification. By that, I mean specify what the correct output is, as a function of the input. I understand that the input is a graph and the output is a tree, but how must the output relate to the input? Presumably if I write an algorithm that outputs an arbitrary tree, you won't be happy. So what requirements must the output satisfy, for the algorithm to count as correct? Please take another try at formulating what your task/question is and edit the question further. Thank you! $\endgroup$ – D.W. Sep 2 '16 at 16:22
  • 1
    $\begingroup$ From your example, I'd infer that (1) the nodes are ordered (A<B<C<D), and that (2) you want the tree to represent all possible paths in the graph, starting from A, with strictly increasing label at each step. ...... is that correct ? $\endgroup$ – tarulen Sep 5 '16 at 10:58
1
$\begingroup$

The problem is under-specified; nonetheless, I will try to help assuming that you are looking for the graph traversal tree.

To obtain such a tree, you can use a graph traversal algorithm such as breadth-first search. You can find a nice implementation of this algorithm in The Algorithm Design Manual by Steven Skiena.

Note that you need to adapt an important aspect of the algorithm:

  • Do not set a node as discovered unless the node has been visited from all of its incoming edges. Without this adaptation, each node will only be visited once, and, therefore, the behaviour of the algorithm will be the same as if multi-edges did not exist.

You will also need a data structure to store the tree of interest. In Skiena's implementation, this data structure is an array that is called parent: if node i is discovered from node j, then parent[i] = j.

The vertex that discovered vertex i is defined as parent[i]. Every vertex is discovered during the course of traversal, so, except for the root, every node has a parent. The parent relation defines a tree of discovery with the initial search node as the root of the tree.

Steven Skiena - The Algorithm Design Manual

However, note that you will need a slightly more complex data structure to support duplicated nodes.

$\endgroup$
-1
$\begingroup$

I have some solution, not sure this is the best:

  • I consider a multiedge as single edge, and I keep track where they appear. This way I have a simple graph.
  • Starting from the root node, I traverse the graph in order to create a tree
  • for each of the multiedges, I clone the sub-tree add it to the parent. This needs to be done bottom-up (from the leaves to the root).
$\endgroup$
  • $\begingroup$ What does it mean that you compress the edges? Anyway from the description any traversal building tree would do, if you are not interested in keeping the graph intact, than bottom-up or top down copy and make it acyclic would work. $\endgroup$ – Evil Sep 2 '16 at 15:53
  • $\begingroup$ I update the part on "compressing" the edges. $\endgroup$ – Stéphane Sep 2 '16 at 16:10
  • 1
    $\begingroup$ Define "best". Which quality measures are you interested in? $\endgroup$ – Raphael Sep 2 '16 at 18:36

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.