LEMON/LEMON-official Changeset - r387:49d9a36b3b84

Repositories » LEMON » LEMON-official

Summary
Changelog
Files
Switch To
- loading...
Options
- Lightweight changelog
- Search
Pull Requests

Changeset - r387:49d9a36b3b84

« 386:5a3d68

389:a0b513 »
388:2d87db »

r387:49d9a36b3b84

Fri, 07 Nov 2008 12:15:16

[Not Reviewed]

0 comments (0 inline)

kpeter (Peter Kovacs)
kpeter@inf.elte.hu

Extend test cases for graphs and digraphs (#172)

0 3 0

default

3 files changed with 431 insertions and 37 deletions:

test/digraph_test.cc

220

test/graph_test.cc

202

test/graph_test.h

↑ Collapse diff ↑

test/digraph_test.cc

Show inline comments

@@ -26,13 +26,13 @@
 		#include "graph_test.h"
 		using namespace lemon;
 		using namespace lemon::concepts;
 		template <class Digraph>
-		void checkDigraph() {
+		void checkDigraphBuild() {
 		  TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
 		  Digraph G;
 		  checkGraphNodeList(G, 0);
 		  checkGraphArcList(G, 0);
@@ -55,13 +55,214 @@
 		  checkGraphInArcList(G, n1, 0);
 		  checkGraphInArcList(G, n2, 1);
 		  checkGraphInArcList(G, n3, 0);
 		  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);
 		  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);
+		}
 		template <class Digraph>
 		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 <class Digraph>
 		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 <class Digraph>
 		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 <class Digraph>
 		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);
@@ -74,15 +275,23 @@
 		  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() {
 		  { // Checking digraph components
 		    checkConcept<BaseDigraphComponent, BaseDigraphComponent >();
 		    checkConcept<IDableDigraphComponent<>,
 		      IDableDigraphComponent<> >();
@@ -166,17 +375,23 @@
 		  check(!g.valid(g.nodeFromId(-1)), "Wrong validity check");
 		  check(!g.valid(g.arcFromId(-1)), "Wrong validity check");
+		}
 		void checkDigraphs() {
 		  { // Checking ListDigraph
-		    checkDigraph<ListDigraph>();
+		    checkDigraphBuild<ListDigraph>();
 		    checkDigraphSplit<ListDigraph>();
 		    checkDigraphAlter<ListDigraph>();
 		    checkDigraphErase<ListDigraph>();
 		    checkDigraphSnapshot<ListDigraph>();
 		    checkDigraphValidityErase<ListDigraph>();
+		  }
 		  { // Checking SmartDigraph
-		    checkDigraph<SmartDigraph>();
+		    checkDigraphBuild<SmartDigraph>();
 		    checkDigraphSplit<SmartDigraph>();
 		    checkDigraphSnapshot<SmartDigraph>();
 		    checkDigraphValidity<SmartDigraph>();
+		  }
+		}
 		int main() {
 		  checkDigraphs();

test/graph_test.cc

Show inline comments

@@ -26,78 +26,244 @@
 		#include "graph_test.h"
 		using namespace lemon;
 		using namespace lemon::concepts;
 		template <class Graph>
-		void checkGraph() {
+		void checkGraphBuild() {
 		  TEMPLATE_GRAPH_TYPEDEFS(Graph);
 		  Graph G;
 		  checkGraphNodeList(G, 0);
 		  checkGraphEdgeList(G, 0);
 		  checkGraphArcList(G, 0);
 		  Node
 		    n1 = G.addNode(),
 		    n2 = G.addNode(),
 		    n3 = G.addNode();
 		  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);
 		  checkGraphEdgeList(G, 1);
 		  checkGraphArcList(G, 2);
 		  checkGraphEdgeList(G, 1);
 		  checkGraphOutArcList(G, n1, 1);
 		  checkGraphOutArcList(G, n2, 1);
-		  checkGraphOutArcList(G, n3, 0);
+		  checkGraphIncEdgeArcLists(G, n1, 1);
 		  checkGraphIncEdgeArcLists(G, n2, 1);
 		  checkGraphIncEdgeArcLists(G, n3, 0);
 		  checkGraphInArcList(G, n1, 1);
 		  checkGraphInArcList(G, n2, 1);
-		  checkGraphInArcList(G, n3, 0);
+		  checkGraphConEdgeList(G, 1);
 		  checkGraphConArcList(G, 2);
 		  checkGraphIncEdgeList(G, n1, 1);
 		  checkGraphIncEdgeList(G, n2, 1);
-		  checkGraphIncEdgeList(G, n3, 0);
+		  Edge e2 = G.addEdge(n2, n1),
 		       e3 = G.addEdge(n2, n3);
 		  checkGraphConArcList(G, 2);
 		  checkGraphConEdgeList(G, 1);
 		  checkGraphNodeList(G, 3);
 		  checkGraphEdgeList(G, 3);
 		  checkGraphArcList(G, 6);
 		  Edge e2 = G.addEdge(n2, n1), e3 = G.addEdge(n2, n3);
 		  checkGraphNodeList(G, 3);
 		  checkGraphArcList(G, 6);
 		  checkGraphEdgeList(G, 3);
 		  checkGraphIncEdgeArcLists(G, n1, 2);
 		  checkGraphIncEdgeArcLists(G, n2, 3);
 		  checkGraphIncEdgeArcLists(G, n3, 1);
 		  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);
 		  checkGraphConEdgeList(G, 3);
 		  checkGraphConArcList(G, 6);
 		  checkGraphConEdgeList(G, 3);
 		  checkArcDirections(G);
 		  checkNodeIds(G);
 		  checkArcIds(G);
 		  checkEdgeIds(G);
 		  checkGraphNodeMap(G);
 		  checkGraphArcMap(G);
 		  checkGraphEdgeMap(G);
+		}
 		template <class Graph>
 		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 <class Graph>
 		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 <class Graph>
 		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 checkConcepts() {
 		  { // Checking graph components
 		    checkConcept<BaseGraphComponent, BaseGraphComponent >();
 		    checkConcept<IDableGraphComponent<>,
 		      IDableGraphComponent<> >();
@@ -231,17 +397,21 @@
 		//     check(g.left(g(0, j)) == INVALID, "Wrong left");
 		//   }
 		// }
 		void checkGraphs() {
 		  { // Checking ListGraph
-		    checkGraph<ListGraph>();
+		    checkGraphBuild<ListGraph>();
 		    checkGraphAlter<ListGraph>();
 		    checkGraphErase<ListGraph>();
 		    checkGraphSnapshot<ListGraph>();
 		    checkGraphValidityErase<ListGraph>();
+		  }
 		  { // Checking SmartGraph
-		    checkGraph<SmartGraph>();
+		    checkGraphBuild<SmartGraph>();
 		    checkGraphSnapshot<SmartGraph>();
 		    checkGraphValidity<SmartGraph>();
+		  }
 		//   { // Checking FullGraph
 		//     FullGraph g(5);
 		//     checkGraphNodeList(g, 5);
 		//     checkGraphEdgeList(g, 10);

test/graph_test.h

Show inline comments

@@ -114,12 +114,21 @@
+		    }
 		    check(e==INVALID,"Wrong IncEdge list linking.");
 		    check(countIncEdges(G,n)==cnt,"Wrong IncEdge number.");
+		  }
 		  template <class Graph>
 		  void checkGraphIncEdgeArcLists(const Graph &G, typename Graph::Node n,
 		                                 int cnt)
+		  {
 		    checkGraphIncEdgeList(G, n, cnt);
 		    checkGraphOutArcList(G, n, cnt);
 		    checkGraphInArcList(G, n, cnt);
+		  }
 		  template <class Graph>
 		  void checkGraphConArcList(const Graph &G, int cnt) {
 		    int i = 0;
 		    for (typename Graph::NodeIt u(G); u != INVALID; ++u) {
 		      for (typename Graph::NodeIt v(G); v != INVALID; ++v) {
 		        for (ConArcIt<Graph> a(G, u, v); a != INVALID; ++a) {
 		          check(G.source(a) == u, "Wrong iterator.");

0 comments (0 inline)

RhodeCode

Login to your account