c++ - 使用 Lemon Graph Library 检查无向图上是否存在边

Question

图表示例：

ListDigraph G;

ListGraph::Node A = G.addNode();
ListGraph::Node B = G.addNode();
ListGraph::Node C = G.addNode();
ListGraph::Node D = G.addNode();

ListGraph::Edge AB = G.addEdge(A,B);
ListGraph::Edge AC = G.addEdge(A,C);
ListGraph::Edge AD = G.addEdge(A,D);
ListGraph::Edge BC = G.addEdge(B,C);
ListGraph::Edge BD = G.addEdge(B,C);
ListGraph::Edge CD = G.addEdge(C,D);

我需要一个以 2 个节点（A 和 C）为例并返回连接这 2 个节点（如果存在）的 Edge 的 ID 的方法。

Answer 1

您可以将节点存储在一维数组中，将边存储在二维数组中。也就是说，不是有节点 A、B、C 和 D，而是有一个带有Nodes[0]through的数组Nodes[3]。然后边 AB 可以存储为Edge[0][1]。您只是将边缘存储为邻接矩阵。然后，您可以使用以下调用找到边缘的 ID G.id(Edge[0][1])：。如果要验证这两个节点之间是否存在边，则只需检查边的 ID 的绝对值是否小于边的总数：

if (abs(G.id(Edge[0][1])) < numberOfEdges)
    return true;
else
    return false;

Answer 2

万一有人（比如我）正在寻找这个，柠檬有findEdge()。你可以这样做：

ListGraph G;
ListGraph::Node A = G.addNode();
ListGraph::Node B = G.addNode();
ListGraph::Node C = G.addNode();
ListGraph::Edge AB = G.addEdge(A, B);
ListGraph::Edge BC = G.addEdge(B, C);

ListGraph::Edge FoundEdge = findEdge(G,A,B); // edge
// print existence:
cout << "Does edge A-B exist? " 
     << (FoundEdge!=INVALID ? "yes" : "no") 
     << endl;