1

エッジがユーザーを自分の興味と結び付ける無向二部グラフを構築したいと考えています。グラフはこのモックアップのようなもので、ユーザーは緑色の円で、関心は赤色の円で表されます。

金利グラフ

2 人のユーザーの類似点を見つけるために、最初のユーザーと 2 番目のユーザーの間で考えられるすべてのパスを見つけようとします。たとえば、ユーザー 0 とユーザー 4 (0 --> 6 --> 2 --> 8 --> 4 と 0 --> 5 --> 1 --> 7 --> 3 の間には 2 つの可能なパスがあります。 --> 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);
    }
}

上記のコードは 1 回しか印刷されませんが、パスが 2 つあるため、2 回印刷されるはずです。

また、この回答に記載されているソリューションを実装しようとしました。ただし、これは 1 つの可能なパスを出力します。では、 QuickGraphを使用して 2 つの頂点間のすべての可能なパスを出力するにはどうすればよいでしょうか?

4

1 に答える 1

1

実際、ユーザー数と選択数が増えると、パスの数が指数関数的に増える可能性があります。100 人のユーザーとアイテムの場合、すべてのユーザーがほとんどのアイテムを好む場合、可能なパスの数は int64 の maxvalue を超える可能性があります。

于 2016-05-17T11:27:17.483 に答える