Changeset 387:49d9a36b3b84 in lemon

Ignore:
Timestamp:
11/07/08 12:15:16 (11 years ago)
Branch:
default
Children:
388:2d87dbd7f8c8, 389:a0b5131b958e
Phase:
public
Message:

Extend test cases for graphs and digraphs (#172)

Location:
test
Files:
3 edited

Unmodified
Added
Removed
• test/digraph_test.cc

 r228 template void checkDigraph() { void checkDigraphBuild() { TEMPLATE_DIGRAPH_TYPEDEFS(Digraph); Digraph G; checkGraphConArcList(G, 1); Arc a2 = G.addArc(n2, n1), a3 = G.addArc(n2, n3), a4 = G.addArc(n2, n3); Arc a2 = G.addArc(n2, n1), a3 = G.addArc(n2, n3), a4 = G.addArc(n2, n3); checkGraphNodeList(G, 3); checkGraphArcList(G, 4); checkGraphNodeMap(G); checkGraphArcMap(G); } } template void checkDigraphSplit() { TEMPLATE_DIGRAPH_TYPEDEFS(Digraph); Digraph G; Node n1 = G.addNode(), n2 = G.addNode(), n3 = G.addNode(); Arc a1 = G.addArc(n1, n2), a2 = G.addArc(n2, n1), a3 = G.addArc(n2, n3), a4 = G.addArc(n2, n3); Node n4 = G.split(n2); check(G.target(OutArcIt(G, n2)) == n4 && G.source(InArcIt(G, n4)) == n2, "Wrong split."); checkGraphNodeList(G, 4); checkGraphArcList(G, 5); checkGraphOutArcList(G, n1, 1); checkGraphOutArcList(G, n2, 1); checkGraphOutArcList(G, n3, 0); checkGraphOutArcList(G, n4, 3); checkGraphInArcList(G, n1, 1); checkGraphInArcList(G, n2, 1); checkGraphInArcList(G, n3, 2); checkGraphInArcList(G, n4, 1); checkGraphConArcList(G, 5); } template void checkDigraphAlter() { TEMPLATE_DIGRAPH_TYPEDEFS(Digraph); Digraph G; Node n1 = G.addNode(), n2 = G.addNode(), n3 = G.addNode(), n4 = G.addNode(); Arc a1 = G.addArc(n1, n2), a2 = G.addArc(n4, n1), a3 = G.addArc(n4, n3), a4 = G.addArc(n4, n3), a5 = G.addArc(n2, n4); checkGraphNodeList(G, 4); checkGraphArcList(G, 5); // Check changeSource() and changeTarget() G.changeTarget(a4, n1); checkGraphNodeList(G, 4); checkGraphArcList(G, 5); checkGraphOutArcList(G, n1, 1); checkGraphOutArcList(G, n2, 1); checkGraphOutArcList(G, n3, 0); checkGraphOutArcList(G, n4, 3); checkGraphInArcList(G, n1, 2); checkGraphInArcList(G, n2, 1); checkGraphInArcList(G, n3, 1); checkGraphInArcList(G, n4, 1); checkGraphConArcList(G, 5); G.changeSource(a4, n3); checkGraphNodeList(G, 4); checkGraphArcList(G, 5); checkGraphOutArcList(G, n1, 1); checkGraphOutArcList(G, n2, 1); checkGraphOutArcList(G, n3, 1); checkGraphOutArcList(G, n4, 2); checkGraphInArcList(G, n1, 2); checkGraphInArcList(G, n2, 1); checkGraphInArcList(G, n3, 1); checkGraphInArcList(G, n4, 1); checkGraphConArcList(G, 5); // Check contract() G.contract(n2, n4, false); checkGraphNodeList(G, 3); checkGraphArcList(G, 5); checkGraphOutArcList(G, n1, 1); checkGraphOutArcList(G, n2, 3); checkGraphOutArcList(G, n3, 1); checkGraphInArcList(G, n1, 2); checkGraphInArcList(G, n2, 2); checkGraphInArcList(G, n3, 1); checkGraphConArcList(G, 5); G.contract(n2, n1); checkGraphNodeList(G, 2); checkGraphArcList(G, 3); checkGraphOutArcList(G, n2, 2); checkGraphOutArcList(G, n3, 1); checkGraphInArcList(G, n2, 2); checkGraphInArcList(G, n3, 1); checkGraphConArcList(G, 3); } template void checkDigraphErase() { TEMPLATE_DIGRAPH_TYPEDEFS(Digraph); Digraph G; Node n1 = G.addNode(), n2 = G.addNode(), n3 = G.addNode(), n4 = G.addNode(); Arc a1 = G.addArc(n1, n2), a2 = G.addArc(n4, n1), a3 = G.addArc(n4, n3), a4 = G.addArc(n3, n1), a5 = G.addArc(n2, n4); // Check arc deletion G.erase(a1); checkGraphNodeList(G, 4); checkGraphArcList(G, 4); checkGraphOutArcList(G, n1, 0); checkGraphOutArcList(G, n2, 1); checkGraphOutArcList(G, n3, 1); checkGraphOutArcList(G, n4, 2); checkGraphInArcList(G, n1, 2); checkGraphInArcList(G, n2, 0); checkGraphInArcList(G, n3, 1); checkGraphInArcList(G, n4, 1); checkGraphConArcList(G, 4); // Check node deletion G.erase(n4); checkGraphNodeList(G, 3); checkGraphArcList(G, 1); checkGraphOutArcList(G, n1, 0); checkGraphOutArcList(G, n2, 0); checkGraphOutArcList(G, n3, 1); checkGraphOutArcList(G, n4, 0); checkGraphInArcList(G, n1, 1); checkGraphInArcList(G, n2, 0); checkGraphInArcList(G, n3, 0); checkGraphInArcList(G, n4, 0); checkGraphConArcList(G, 1); } template void checkDigraphSnapshot() { TEMPLATE_DIGRAPH_TYPEDEFS(Digraph); Digraph G; Node n1 = G.addNode(), n2 = G.addNode(), n3 = G.addNode(); Arc a1 = G.addArc(n1, n2), a2 = G.addArc(n2, n1), a3 = G.addArc(n2, n3), a4 = G.addArc(n2, n3); typename Digraph::Snapshot snapshot(G); Node n = G.addNode(); G.addArc(n3, n); G.addArc(n, n3); checkGraphNodeList(G, 4); checkGraphArcList(G, 6); snapshot.restore(); checkGraphNodeList(G, 3); checkGraphArcList(G, 4); checkGraphOutArcList(G, n1, 1); checkGraphOutArcList(G, n2, 3); checkGraphOutArcList(G, n3, 0); checkGraphInArcList(G, n1, 1); checkGraphInArcList(G, n2, 1); checkGraphInArcList(G, n3, 2); checkGraphConArcList(G, 4); checkNodeIds(G); checkArcIds(G); checkGraphNodeMap(G); checkGraphArcMap(G); G.addNode(); snapshot.save(G); G.addArc(G.addNode(), G.addNode()); snapshot.restore(); checkGraphNodeList(G, 4); checkGraphArcList(G, 4); } void checkConcepts() { void checkDigraphs() { { // Checking ListDigraph checkDigraph(); checkDigraphBuild(); checkDigraphSplit(); checkDigraphAlter(); checkDigraphErase(); checkDigraphSnapshot(); checkDigraphValidityErase(); } { // Checking SmartDigraph checkDigraph(); checkDigraphBuild(); checkDigraphSplit(); checkDigraphSnapshot(); checkDigraphValidity(); }
• test/graph_test.cc

 r228 template void checkGraph() { void checkGraphBuild() { TEMPLATE_GRAPH_TYPEDEFS(Graph); checkGraphNodeList(G, 0); checkGraphEdgeList(G, 0); checkGraphArcList(G, 0); Node checkGraphNodeList(G, 3); checkGraphEdgeList(G, 0); checkGraphArcList(G, 0); Edge e1 = G.addEdge(n1, n2); check((G.u(e1) == n1 && G.v(e1) == n2) || (G.u(e1) == n2 && G.v(e1) == n1), "Wrong edge"); checkGraphNodeList(G, 3); checkGraphNodeList(G, 3); checkGraphEdgeList(G, 1); checkGraphArcList(G, 2); checkGraphEdgeList(G, 1); checkGraphOutArcList(G, n1, 1); checkGraphOutArcList(G, n2, 1); checkGraphOutArcList(G, n3, 0); checkGraphInArcList(G, n1, 1); checkGraphInArcList(G, n2, 1); checkGraphInArcList(G, n3, 0); checkGraphIncEdgeList(G, n1, 1); checkGraphIncEdgeList(G, n2, 1); checkGraphIncEdgeList(G, n3, 0); checkGraphIncEdgeArcLists(G, n1, 1); checkGraphIncEdgeArcLists(G, n2, 1); checkGraphIncEdgeArcLists(G, n3, 0); checkGraphConEdgeList(G, 1); checkGraphConArcList(G, 2); checkGraphConEdgeList(G, 1); Edge e2 = G.addEdge(n2, n1), e3 = G.addEdge(n2, n3); checkGraphNodeList(G, 3); Edge e2 = G.addEdge(n2, n1), e3 = G.addEdge(n2, n3); checkGraphNodeList(G, 3); checkGraphEdgeList(G, 3); checkGraphArcList(G, 6); checkGraphEdgeList(G, 3); checkGraphOutArcList(G, n1, 2); checkGraphOutArcList(G, n2, 3); checkGraphOutArcList(G, n3, 1); checkGraphInArcList(G, n1, 2); checkGraphInArcList(G, n2, 3); checkGraphInArcList(G, n3, 1); checkGraphIncEdgeList(G, n1, 2); checkGraphIncEdgeList(G, n2, 3); checkGraphIncEdgeList(G, n3, 1); checkGraphIncEdgeArcLists(G, n1, 2); checkGraphIncEdgeArcLists(G, n2, 3); checkGraphIncEdgeArcLists(G, n3, 1); checkGraphConEdgeList(G, 3); checkGraphConArcList(G, 6); checkGraphConEdgeList(G, 3); checkArcDirections(G); checkGraphArcMap(G); checkGraphEdgeMap(G); } template void checkGraphAlter() { TEMPLATE_GRAPH_TYPEDEFS(Graph); Graph G; Node n1 = G.addNode(), n2 = G.addNode(), n3 = G.addNode(), n4 = G.addNode(); Edge e1 = G.addEdge(n1, n2), e2 = G.addEdge(n2, n1), e3 = G.addEdge(n2, n3), e4 = G.addEdge(n1, n4), e5 = G.addEdge(n4, n3); checkGraphNodeList(G, 4); checkGraphEdgeList(G, 5); checkGraphArcList(G, 10); // Check changeU() and changeV() if (G.u(e2) == n2) { G.changeU(e2, n3); } else { G.changeV(e2, n3); } checkGraphNodeList(G, 4); checkGraphEdgeList(G, 5); checkGraphArcList(G, 10); checkGraphIncEdgeArcLists(G, n1, 3); checkGraphIncEdgeArcLists(G, n2, 2); checkGraphIncEdgeArcLists(G, n3, 3); checkGraphIncEdgeArcLists(G, n4, 2); checkGraphConEdgeList(G, 5); checkGraphConArcList(G, 10); if (G.u(e2) == n1) { G.changeU(e2, n2); } else { G.changeV(e2, n2); } checkGraphNodeList(G, 4); checkGraphEdgeList(G, 5); checkGraphArcList(G, 10); checkGraphIncEdgeArcLists(G, n1, 2); checkGraphIncEdgeArcLists(G, n2, 3); checkGraphIncEdgeArcLists(G, n3, 3); checkGraphIncEdgeArcLists(G, n4, 2); checkGraphConEdgeList(G, 5); checkGraphConArcList(G, 10); // Check contract() G.contract(n1, n4, false); checkGraphNodeList(G, 3); checkGraphEdgeList(G, 5); checkGraphArcList(G, 10); checkGraphIncEdgeArcLists(G, n1, 4); checkGraphIncEdgeArcLists(G, n2, 3); checkGraphIncEdgeArcLists(G, n3, 3); checkGraphConEdgeList(G, 5); checkGraphConArcList(G, 10); G.contract(n2, n3); checkGraphNodeList(G, 2); checkGraphEdgeList(G, 3); checkGraphArcList(G, 6); checkGraphIncEdgeArcLists(G, n1, 4); checkGraphIncEdgeArcLists(G, n2, 2); checkGraphConEdgeList(G, 3); checkGraphConArcList(G, 6); } template void checkGraphErase() { TEMPLATE_GRAPH_TYPEDEFS(Graph); Graph G; Node n1 = G.addNode(), n2 = G.addNode(), n3 = G.addNode(), n4 = G.addNode(); Edge e1 = G.addEdge(n1, n2), e2 = G.addEdge(n2, n1), e3 = G.addEdge(n2, n3), e4 = G.addEdge(n1, n4), e5 = G.addEdge(n4, n3); // Check edge deletion G.erase(e2); checkGraphNodeList(G, 4); checkGraphEdgeList(G, 4); checkGraphArcList(G, 8); checkGraphIncEdgeArcLists(G, n1, 2); checkGraphIncEdgeArcLists(G, n2, 2); checkGraphIncEdgeArcLists(G, n3, 2); checkGraphIncEdgeArcLists(G, n4, 2); checkGraphConEdgeList(G, 4); checkGraphConArcList(G, 8); // Check node deletion G.erase(n3); checkGraphNodeList(G, 3); checkGraphEdgeList(G, 2); checkGraphArcList(G, 4); checkGraphIncEdgeArcLists(G, n1, 2); checkGraphIncEdgeArcLists(G, n2, 1); checkGraphIncEdgeArcLists(G, n4, 1); checkGraphConEdgeList(G, 2); checkGraphConArcList(G, 4); } template void checkGraphSnapshot() { TEMPLATE_GRAPH_TYPEDEFS(Graph); Graph G; Node n1 = G.addNode(), n2 = G.addNode(), n3 = G.addNode(); Edge e1 = G.addEdge(n1, n2), e2 = G.addEdge(n2, n1), e3 = G.addEdge(n2, n3); checkGraphNodeList(G, 3); checkGraphEdgeList(G, 3); checkGraphArcList(G, 6); typename Graph::Snapshot snapshot(G); Node n = G.addNode(); G.addEdge(n3, n); G.addEdge(n, n3); G.addEdge(n3, n2); checkGraphNodeList(G, 4); checkGraphEdgeList(G, 6); checkGraphArcList(G, 12); snapshot.restore(); checkGraphNodeList(G, 3); checkGraphEdgeList(G, 3); checkGraphArcList(G, 6); checkGraphIncEdgeArcLists(G, n1, 2); checkGraphIncEdgeArcLists(G, n2, 3); checkGraphIncEdgeArcLists(G, n3, 1); checkGraphConEdgeList(G, 3); checkGraphConArcList(G, 6); checkNodeIds(G); checkEdgeIds(G); checkArcIds(G); checkGraphNodeMap(G); checkGraphEdgeMap(G); checkGraphArcMap(G); G.addNode(); snapshot.save(G); G.addEdge(G.addNode(), G.addNode()); snapshot.restore(); checkGraphNodeList(G, 4); checkGraphEdgeList(G, 3); checkGraphArcList(G, 6); } void checkGraphs() { { // Checking ListGraph checkGraph(); checkGraphBuild(); checkGraphAlter(); checkGraphErase(); checkGraphSnapshot(); checkGraphValidityErase(); } { // Checking SmartGraph checkGraph(); checkGraphBuild(); checkGraphSnapshot(); checkGraphValidity(); }
• test/graph_test.h

 r263 check(e==INVALID,"Wrong IncEdge list linking."); check(countIncEdges(G,n)==cnt,"Wrong IncEdge number."); } template void checkGraphIncEdgeArcLists(const Graph &G, typename Graph::Node n, int cnt) { checkGraphIncEdgeList(G, n, cnt); checkGraphOutArcList(G, n, cnt); checkGraphInArcList(G, n, cnt); }
Note: See TracChangeset for help on using the changeset viewer.