All simple paths in Multigraph (Depth First Traversal)

Question

After reading and searching for quite a while, I still can't get my head around Depth First Traversal (or Search) of a Multigraph (two vertices can have more than one edge).

I found this answer on another SO question:

Graph Algorithm To Find All Connections Between Two Arbitrary Vertices

which is a good answer, but it applies only on Simple Graphs.

So in short, I need all simple paths (no repeating vertices) from vertex A to Vertex B in a Multigraph, not just the shortest.

I'm implementing this in Java, using JGraphT, if that is of any help. I don't mind a solution in another language. The graph is directed, and weighted, if this also of any help.

P.S. I'm not concerned about the running time of the algorithm (I will cache the results).

I'm looking for output similar to the one in the linked question (I have some more information attached to the edges, but that doesn't have much to do with the traversal:

All paths connecting B to E:
B->E
B->F->E
B->F->C->E
B->A->C->E
B->A->C->F->E

Thank you.

What sort of output or return value or result are you looking for? — joshlf, Jul 18 '13 at 16:32
Seems like you could use some sort of recursive backtracking algorithm. Non-promising nodes would be those already visited. — nattyddubbs, Jul 18 '13 at 16:38
@nattyddubbs The best algorithm for this is a Depth First Search/Traversal, doesn't matter if it's recursive or iterative, as long as it gives the correct output format — ekstrakt, Jul 18 '13 at 16:41
@ekstrakt a depth first search is a specific form of backtracking. We are saying the same thing ;) — nattyddubbs, Jul 18 '13 at 16:45

score 2 · Answer 1 · answered Jul 18 '13 at 16:50

Multigraphs and normal graphs shouldn't actually require different code. In both cases, you're going to need to know whether you've visited a given node on this particular path in the past. That works regardless of how many edges can connect two vertices.

Thus, what you're going to want to do is, for each path, keep a list of the vertices you've already visited, and never travel to an already-visited vertex. Thus, some pseudocode:

function DFSHelper(vertex v, array visited):
    for edge in v.edges:
        if edge.vertex_at_end not in visited:
            DFSHelper(edge.vertex_at_end, visited + [edge.vertex_at_end])
    for v in visited:
        print v + "->"

function DFS(vertex v):
    DFSHelper(v, [])

Adjust as appropriate (for example, this currently prints all subpaths of a given path, like "A", "A->B", "A->B->C", etc).

Also note that this will print some paths twice (if there are multiple edges between the same pair of vertices). You can adjust to eliminate this behavior by only traveling to vertex A from vertex B once in a given function (that is, if multiple edges connect the two, only recurse on the first edge, and ignore the rest).

score 0 · Answer 2 · answered Jul 18 '13 at 16:33

This is an implementation of DFS Search in C. Can be modified to work with MultiGraphs imo.

If this is what you are looking for, I can modify it to work with 'MultiGraphs'..

#include <stdio.h>
#include <malloc.h>
#include <conio.h>

typedef struct AdjacencyList
{
    char VertexID;
    int *IncidenceList;
}AdjList;

typedef struct Graph
{
    int VertexCount, Status;
    char VertexName;
    AdjList List;
    struct Graph *Next;
}Graph;

Graph* InitializeGraph();
Graph *InitGraphNode(int cnt);
void PerformDepthFirstSearch(Graph *graph);

int main()
{
    Graph *graph;
    graph = InitializeGraph();
    PerformDepthFirstSearch(graph);
    return 0;
}

Graph *InitGraphNode(int cnt)
{
    Graph *node = ((Graph*)malloc(sizeof(Graph)));
    node->List.IncidenceList = ((int*)malloc(sizeof(int)*cnt));
    node->Next = NULL;
    return node;
}

Graph* InitializeGraph()
{
    Graph *graphHead = NULL, *node, *tmp, *tmp2;
    char vname;
    int cnt, i, j, isIncident = 0;
    printf("Enter the number of vertices : ");
    scanf("%d", &cnt);
    if (cnt == 0)
    {
        printf("Number of vertices cannot be ZERO!!\n\n");
        return graphHead;
    }
    graphHead = InitGraphNode(1);
    graphHead->VertexCount = cnt;
    for(i = 0; i < cnt; i++)
    {
        printf("VertexName : ");
        vname = getche();
        printf("\n");
        node = InitGraphNode(cnt);
        node->VertexName = vname;
        node->Next = NULL;
        node->Status = 1;
        if (graphHead->Next == NULL)
        {
            graphHead->Next = node;
        }
        else
        {
            tmp = graphHead;
            while (tmp->Next != NULL)
            {
                tmp = tmp->Next;
            }
            tmp->Next = node;
        }
    }
    tmp = graphHead->Next;
    printf("Prepare to input the adjacent elements of corresponding vertices...\n\n");
    for(i = 0; i < cnt; i++)
    {
        vname = tmp->VertexName;
        tmp2 = graphHead->Next;
        for(j = 0; j < cnt; j++)
        {
        here :
            printf("%c incident on %c :: (1 for YES)(0 for NO) ::-> ",vname, tmp2->VertexName);
            scanf("%d", &isIncident);
            if ((isIncident < 0)||(isIncident > 1))
            {
                printf("Wrong Input!! Try again!!\n\n");
                goto here;
            }
            tmp->List.IncidenceList[j] = isIncident;
            tmp2 = tmp2->Next;
        }
        tmp = tmp->Next;
    }
    return graphHead;
}

void PerformDepthFirstSearch(Graph *graph)
{
    Graph *Stack[100], *Copy = graph->Next, *node, *tmp = graph->Next;
    int top = 0, i, cnt = 0;
    Stack[top++] = Copy;
    Copy->Status++;
    while(top != 0)
    {
        node = Stack[--top];
        node->Status++;
        printf("%c, ", node->VertexName);
        for(i = 0; i < graph->VertexCount; i++)
        {
            if(node->List.IncidenceList[i] == 1)
            {
                while (cnt < i)
                {
                    tmp = tmp->Next;
                    cnt++;
                }
                if (tmp->Status == 1)
                {
                    Stack[top++] = tmp;
                    tmp->Status++;
                }
            }
        }
    }
}

I'm not really sure how/if this can be modified for multigraphs, because it uses adjacency/incidence lists between vertices to track neighboring edges. — ekstrakt, Jul 18 '13 at 16:53
One Vertex can always have more than one adjacent vertices, isn't it ? — Priyabrata, Jul 18 '13 at 16:56
Yes, but it can have multiple Edges connecting it to the adjacent vertex, which I'm not sure how it is implemented using adjacency list... — ekstrakt, Jul 18 '13 at 17:00
I see. You are right.. But that problem can be solved using an Edge flagging i.e a simple flag to denote more than one connection between any two vertices, and another to hold the count of the 'extra' edge should do the trick. — Priyabrata, Jul 18 '13 at 17:04
The thing is, I need to be able to select which edge I'm traversing, because it is a directed and weighted graph. I need to traverse every edge, and get a list of paths. Only at the end I'll select the most suitable path. — ekstrakt, Jul 18 '13 at 17:08
Say we have 4 vertices. (A, B, C, D). A --> B, A --> C, C --> D, D --> B.So the two possible ways of reacing B are : 1) A --> B (Traversing the Direct Edge provided the weight is least), 2) Traversing the indirect route A --> C, C --> D, D --> B, if Sum of the weights is minumum compared to the direct edge. So, first we need to get a list of paths, connecting A and B. To do that, Start from vertex A(where each vertex is considered as a structure/class address having n parts, where n is the no. of edges going out of the vertex) and see if it ends in Destination B. Trace each path — Priyabrata, Jul 18 '13 at 17:36
and store the sum of weights. The path having minimum weight gets selected. The graph being directed makes the task simpler imo. In case of any assitance with code, I'll try my best :) — Priyabrata, Jul 18 '13 at 17:38

All simple paths in Multigraph (Depth First Traversal)

2 Answers2