Finding all possible paths between two vertices in quickgraph

Question

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.

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?

score 1 · Answer 1 · answered May 17 '16 at 11:27

1

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.

answered May 17 '16 at 11:27

Wojciech Kozaczewski

326
1
5

Hmm..thanks for bringing that up. I was doing this project as a part of building a recommender that recommends users based on their similar items. I was thinking of using graphs as they're easy to implement and visualize. However, you're right, that could lead to very large number of paths. Do you have any suggestions? – xabush May 17 '16 at 12:06
One way is to focus on paths of a limited length - for example there are no more than O(n^k) paths of length below k. For n=100 and k=3 this is one million paths which is acceptable in some cases. To find similarity of 2 users, you can count the size of their common favourite items, or maybe (number of common items)/(items of User1 + items of User2); this one is simple. EDIT: don't worry about this O(n^k). You can easily count this using dynamic programming in time O(nk) which is way better for like n<10^6, k<10. You still probably want to treat SHORT connections as more important. – Wojciech Kozaczewski May 17 '16 at 12:26
what do you mean by using dynamic programming in this context? – xabush May 19 '16 at 09:36

Finding all possible paths between two vertices in quickgraph

1 Answers1