-1
$\begingroup$

I have an undirected graph and i want to list all possible paths from a starting node. Each connection between 2 nodes is unique in a listed path is unique, for example give this graph representation:

{A: [B, C, D],
 B: [A, C, D],
 C: [A, B, D],
 D: [A, B, C]}

some listed path starting from A

A, B, C, D, A, C  in this path we have a connection between
A and B but we can't have a connection between B and A(since A and b are already connected)

I can't accomplish it using the existing algorithm that i know like DFS . Any help will be very appreciated .

Improve this question
$\endgroup$
2
  • $\begingroup$ Try a search for similar questions, such as mathoverflow.net/questions/18603/…. $\endgroup$
    – Ed Wynn
    Commented Sep 13, 2018 at 13:33
  • $\begingroup$ if the graph is undirected, why do you have redundant information such as a link from $A$ to $B$ as well as a link from $B$ to $A$? $\endgroup$
    – David G. Stork
    Commented Sep 13, 2018 at 16:33

1 Answer 1

Reset to default
2
$\begingroup$

Just list them, brute force.
For every edge $(A,X_i)$ define a subgraph by deleting that edge. In the subgraph, recursively enumerate all paths starting at $X_i$, then for every such path add the edge $(A,X_i)$ at the start and you have all paths.

This might seem inefficient, but as you are creating a giant list of paths it is actually not (it is, in fact, linear in the size of the list you are trying to create).

Improve this answer
$\endgroup$
4
  • $\begingroup$ do you have some code please? $\endgroup$
    – lafi raed
    Commented Sep 13, 2018 at 10:52
  • 2
    $\begingroup$ This is a page for research level math, if you want someone to write your code for you this is the wrong place, sorry. You could try on CS pages, but also there people will most likely not do your work. $\endgroup$
    – Dirk
    Commented Sep 13, 2018 at 10:54
  • $\begingroup$ no sorry , i mean if there is an algorithm or a paper that describe it it will help me better $\endgroup$
    – lafi raed
    Commented Sep 13, 2018 at 10:55
  • $\begingroup$ I might have seen this problem as a homework in an algorithm class once, but I don't know of any paper for that, sorry. However, the algorithm should not be that hard to build yourself, it is just straight forward recursion (and yes, I am aware of the joke I made there). $\endgroup$
    – Dirk
    Commented Sep 13, 2018 at 10:56

Not the answer you're looking for? Browse other questions tagged .