all paths between two nodes

[bytesanil]

Hi all,

I am trying to find out what is the best (time efficient) algorithm to accomplish the task described below.

I have a set of records. For this set of records I have connection data which indicates how pairs of records from this set connect to one another (basically a graph, the records being the vertices and the connection data the edges).

All of the records in the set have connection information (i.e. no orphan records are present; each record in the set connects to one or more other records in the set).

I want to choose any two (arbitrary) records from the set and be able to show all ways possible the chosen records connect (either directly or through other connections).

For example:

If I have the following records:
A, B, C, D, E

and the following represents the connections(links):
(A,B),(A,C),(B,A),(B,D),(B,E),(B,F),(C,A),(C,E),
(C,F),(D,B),(E,C),(E,F),(F,B),(F,C),(F,E)

[where (A,B) means record A connects to record B]
If I chose B as my starting record and E as my ending record, I would want to find all paths through the record connections that would connect record B to record E.

All paths connecting B to E:
B->E
B->F->E
B->F->C->E
B->A->C->E
B->A->C->F->E
This is an example, in practice I may have sets containing hundreds of thousands of records

I can go for c/c++.
Guide me in accomplishing the task.

Thanks,
Anil Kumar Y.

[jkmyoung]

I'm assuming that you can't use the same node twice?
I suggest marking which nodes you've used by having it in some string, say path. Pseudocode:

start -> end
Mark start node.
current = start.
String path += start // stringwise
 
FindPath()
 
FindPath(){
  for each connection -> node j from current node
    if j is not in path{
      path += j  // stringwise
      current = j
      if (j = end) Print path
      else FindPath() //recurse
 
      path -= j // stringwise, so we can reset to the original state.
    }
}

If this pseudocode is too complicated, you can always find your own original method for tackling this problem.

[donbock]

Where did this problem come from?

Hundreds of thousands of nodes ... I don't remember why, but I have a strong feeling that this problem is not NP unless there are severe constraints on the connectedness of your graph.

I recommend you look into graph theory before embarking on an implementation.

[weaknessforcats]

B->E
B->F->E
B->F->C->E
B->A->C->E
B->A->C->F->E

You can probably use a multiset container for this.

You would add to the container:

B->E
B->F
B->A
F->E
F->C
A->C

Now to query on B create a temporary multiset containing all connections to B:

F->E
F->C
A->C

where B->E is part of your result.

Now query on F and A separately. For F a temporary multiset woudl contain:

F->C

Since the original query is on B, F->E represents B->F->E.

Repeat and query on C:

C->E
C->F

Since the original query is on B, then F, C->E represents
B->F->C->E.

C->F is ignored since this is a circular reference to F (the current query).

This concludes the F leg so you now have all B->F-> etc... C

Now do the A leg. You have A->C so create a temporary multiset for all C connections:

C->E
C->F

C->E is part of your result an represents B->A->C->E. The temporary multiset contains:

F->E

This represents B->A->C->F->E.

There are no entries for the temporary multiset, so you are done.

Hence the total query result is:

B->E
B->F->E
B->F->C->E
B->A->C->E
B->A->C->F->E

[donbock]

@donbock
Apparently I was needlessly pessimistic. I think the OP is referring to the classic all simple paths problem. There are suggested solutions all over the internet.

[jkmyoung]

In the worst case, there are all connections, resulting in a n! time. It definitely is not np.

I guess my initial response was the depth first search.

There may be optimizations, by storing subpaths, but then you have to compare subpath to subpath to avoid intersection. One way you could check if a node is in a path is as follows:
Number the nodes, 0 -> n-1.
Create an n bit number which represents the nodes used in the path, initially set to 0. When you encounter a node, say i, set the ith bit, or 1 << i. When coming back from the recursive call, unset 1 << i.

Comparing 2 paths, you simply take the bitwise & of the 2 numbers, and if there are any intersections, the result will not be 0.
====
The multiset implementation is interesting too! Reminds me of prolog. My worry is that it would be inefficient, but I can't quite figure out how to calculate on the runtime.