CODEWITHSUNDEEP
c#graphgraph-theoryquickgraph
xabush
xabush

Reputation: 877

Finding all possible paths between two vertices in quickgraph

I want to build an undirected bipartite graph where an edge connects a user with his/her interests. The graph looks something like this mock up, where users are represented by green circles and interests by red circles.

Interest graph

To find the similarity between two users, I try to find all the possible paths between the first user and the second user. For example, there are two possible paths between User 0 and User 4(0 --> 6 --> 2 --> 8 --> 4 and 0 --> 5 --> 1 --> 7 --> 3 --> 8 --> 4). This is what I tried so far:

private int v = 4;
public static void Main()
{
    var graph = new UndirectedGraph<int, SEdge<int>>();
    List<int> vertices = new List<int>();
    for (int i = 0; i < 11; i++)
    {
        vertices.Add(i);
    }

    graph.AddVertexRange(vertices);
    //Edges incident to 0
    graph.AddEdge(new SEdge<int>(vertices[0], vertices[5]));
    graph.AddEdge(new SEdge<int>(vertices[0], vertices[6]));  
    //Edges incident to 1
    graph.AddEdge(new SEdge<int>(vertices[1], vertices[5]));
    graph.AddEdge(new SEdge<int>(vertices[1], vertices[6]));
    //Edges incident to 2
    graph.AddEdge(new SEdge<int>(vertices[2], vertices[6]));
    graph.AddEdge(new SEdge<int>(vertices[2], vertices[8]));
    //Edges incident to 3
    graph.AddEdge(new SEdge<int>(vertices[3], vertices[7]));
    graph.AddEdge(new SEdge<int>(vertices[3], vertices[8]));
    //Edges incident to 4
    graph.AddEdge(new SEdge<int>(vertices[4], vertices[8]));

    Func<SEdge<int>, double> edgeWeights = se => 1.0;
    //Vertex distance observer
    var observer = new UndirectedVertexPredecessorRecorderObserver<int, SEdge<int>>();

    //DFS Algortihm
    var dfs = new UndirectedDepthFirstSearchAlgorithm<int, SEdge<int>>(graph);
//    dfs.FinishVertex += VertexFinished;
//    dfs.ForwardOrCrossEdge += TransverseEdge;
    dfs.TreeEdge += TransverseEdge;
    dfs.Compute(0);        
}

public void TransverseEdge(object sender, EdgeEventArgs<int, SEdge<int>> ed){
    if(ed.Edge.Source == v){
        Console.WriteLine("Visited {0}", ed.Edge.Source);
    }
}

The above code only prints one times but it should be printing twice as there are two paths.

I also tried to implement the solution given in this answer. However, that prints one possible path. So, how can I use QuickGraph to print all the possible paths between two vertices?

Upvotes: 1

Views: 1401

Answers (1)

Wojciech Kozaczewski
Wojciech Kozaczewski

Reputation: 326

Actually, the number of paths might grow exponentially when number of users and selection grows. For 100 users and items if all users like most items it is likely that the number of possible paths will exceed maxvalue of int64.

Upvotes: 1

Related Questions