Поиск всех возможных путей между двумя вершинами в quickgraph

Question

Я хочу построить неориентированный двудольный граф, где край соединяет пользователя с его/ее интересами. Граф выглядит примерно так, как будто это макет, где пользователи представлены зелеными кругами и интересами красных кругов.

Чтобы найти сходство между двумя пользователями, я пытаюсь найти все возможные пути между первым пользователем и вторым пользователем. Например, существует два возможных пути между пользователем 0 и пользователем 4 (0 -> 6 -> 2 -> 8 -> 4 и 0 -> 5 -> 1 -> 7 -> 3 -> 8 -> 4). Это то, что я пытался до сих пор:

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); 
    } 
} 

Приведенный выше код печатает только один раз, но она должна быть печать в два раза есть два пути.

Я также попытался реализовать решение, данное в ответе this. Тем не менее, это печатает один возможный путь. Итак, как я могу использовать QuickGraph для печати всех возможных путей между двумя вершинами?

Answer 1

Фактически, количество путей может расти экспоненциально, когда число пользователей и выбор возрастает. Для 100 пользователей и элементов, если всем пользователям нравится большинство элементов, вероятно, количество возможных путей превысит максимальное значение int64.