1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/src/demo/dijkstra_demo.cc	Thu Mar 03 17:18:27 2005 +0000
     1.3 @@ -0,0 +1,75 @@
     1.4 +#include <iostream>
     1.5 +
     1.6 +#include <lemon/list_graph.h>
     1.7 +#include <lemon/dijkstra.h>
     1.8 +
     1.9 +using namespace lemon;
    1.10 +
    1.11 +
    1.12 +int main (int, char*[])
    1.13 +{
    1.14 +
    1.15 +    typedef ListGraph Graph;
    1.16 +    typedef Graph::Node Node;
    1.17 +    typedef Graph::Edge Edge;
    1.18 +    typedef Graph::EdgeMap<int> LengthMap;
    1.19 +
    1.20 +    Graph g;
    1.21 +
    1.22 +    //An example from Ahuja's book
    1.23 +
    1.24 +    Node s=g.addNode();
    1.25 +    Node v2=g.addNode();
    1.26 +    Node v3=g.addNode();
    1.27 +    Node v4=g.addNode();
    1.28 +    Node v5=g.addNode();
    1.29 +    Node t=g.addNode();
    1.30 +
    1.31 +    Edge s_v2=g.addEdge(s, v2);
    1.32 +    Edge s_v3=g.addEdge(s, v3);
    1.33 +    Edge v2_v4=g.addEdge(v2, v4);
    1.34 +    Edge v2_v5=g.addEdge(v2, v5);
    1.35 +    Edge v3_v5=g.addEdge(v3, v5);
    1.36 +    Edge v4_t=g.addEdge(v4, t);
    1.37 +    Edge v5_t=g.addEdge(v5, t);
    1.38 +  
    1.39 +    LengthMap len(g);
    1.40 +
    1.41 +    len.set(s_v2, 10);
    1.42 +    len.set(s_v3, 10);
    1.43 +    len.set(v2_v4, 5);
    1.44 +    len.set(v2_v5, 8);
    1.45 +    len.set(v3_v5, 5);
    1.46 +    len.set(v4_t, 8);
    1.47 +    len.set(v5_t, 8);
    1.48 +
    1.49 +    std::cout << "The id of s is " << g.id(s)<< ", the id of t is " << g.id(t)<<"."<<std::endl;
    1.50 +
    1.51 +    std::cout << "Dijkstra algorithm test..." << std::endl;
    1.52 +
    1.53 +    Dijkstra<Graph, LengthMap> dijkstra_test(g,len);
    1.54 +    
    1.55 +    dijkstra_test.run(s);
    1.56 +
    1.57 +    
    1.58 +    std::cout << "The distance of node t from node s: " << dijkstra_test.dist(t)<<std::endl;
    1.59 +
    1.60 +    std::cout << "The shortest path from s to t goes through the following nodes (the first one is t, the last one is s): "<<std::endl;
    1.61 +
    1.62 +    for (Node v=t;v != s; v=dijkstra_test.predNode(v)){
    1.63 +	std::cout << g.id(v) << "<-";
    1.64 +    }
    1.65 +    std::cout << g.id(s) << std::endl;	
    1.66 +    
    1.67 +
    1.68 +    return 0;
    1.69 +}
    1.70 +
    1.71 +
    1.72 +
    1.73 +
    1.74 +
    1.75 +
    1.76 +
    1.77 +
    1.78 +

     2.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     2.2 +++ b/src/demo/kruskal_demo.cc	Thu Mar 03 17:18:27 2005 +0000
     2.3 @@ -0,0 +1,95 @@
     2.4 +#include <iostream>
     2.5 +#include <vector>
     2.6 +
     2.7 +#include <lemon/maps.h>
     2.8 +#include <lemon/kruskal.h>
     2.9 +#include <lemon/list_graph.h>
    2.10 +
    2.11 +
    2.12 +using namespace std;
    2.13 +using namespace lemon;
    2.14 +
    2.15 +
    2.16 +int main() {
    2.17 +
    2.18 +  typedef ListGraph::Node Node;
    2.19 +  typedef ListGraph::Edge Edge;
    2.20 +  typedef ListGraph::NodeIt NodeIt;
    2.21 +  typedef ListGraph::EdgeIt EdgeIt;
    2.22 +
    2.23 +  ListGraph G;
    2.24 +
    2.25 +  Node s=G.addNode();
    2.26 +  Node v1=G.addNode();
    2.27 +  Node v2=G.addNode();
    2.28 +  Node v3=G.addNode();
    2.29 +  Node v4=G.addNode();
    2.30 +  Node t=G.addNode();
    2.31 +  
    2.32 +  Edge e1 = G.addEdge(s, v1);
    2.33 +  Edge e2 = G.addEdge(s, v2);
    2.34 +  Edge e3 = G.addEdge(v1, v2);
    2.35 +  Edge e4 = G.addEdge(v2, v1);
    2.36 +  Edge e5 = G.addEdge(v1, v3);
    2.37 +  Edge e6 = G.addEdge(v3, v2);
    2.38 +  Edge e7 = G.addEdge(v2, v4);
    2.39 +  Edge e8 = G.addEdge(v4, v3);
    2.40 +  Edge e9 = G.addEdge(v3, t);
    2.41 +  Edge e10 = G.addEdge(v4, t);
    2.42 +
    2.43 +  typedef ListGraph::EdgeMap<int> ECostMap;
    2.44 +  typedef ListGraph::EdgeMap<bool> EBoolMap;
    2.45 +
    2.46 +  ECostMap edge_cost_map(G, 2);
    2.47 +  EBoolMap tree_map(G);
    2.48 +  
    2.49 +
    2.50 +  //Test with const map.
    2.51 +  std::cout << "The weight of the minimum spanning tree is " << kruskalEdgeMap(G, ConstMap<ListGraph::Edge,int>(2), tree_map)<<std::endl;
    2.52 +
    2.53 +/*
    2.54 +  ==10,
    2.55 +	"Total cost should be 10");
    2.56 +  //Test with a edge map (filled with uniform costs).
    2.57 +  check(kruskalEdgeMap(G, edge_cost_map, tree_map)==10,
    2.58 +	"Total cost should be 10");
    2.59 +
    2.60 +  edge_cost_map.set(e1, -10);
    2.61 +  edge_cost_map.set(e2, -9);
    2.62 +  edge_cost_map.set(e3, -8);
    2.63 +  edge_cost_map.set(e4, -7);
    2.64 +  edge_cost_map.set(e5, -6);
    2.65 +  edge_cost_map.set(e6, -5);
    2.66 +  edge_cost_map.set(e7, -4);
    2.67 +  edge_cost_map.set(e8, -3);
    2.68 +  edge_cost_map.set(e9, -2);
    2.69 +  edge_cost_map.set(e10, -1);
    2.70 +
    2.71 +  vector<Edge> tree_edge_vec;
    2.72 +
    2.73 +  //Test with a edge map and inserter.
    2.74 +  check(kruskalEdgeMap_IteratorOut(G, edge_cost_map,
    2.75 +				   back_inserter(tree_edge_vec))
    2.76 +	==-31,
    2.77 +	"Total cost should be -31.");
    2.78 +
    2.79 +  tree_edge_vec.clear();
    2.80 +
    2.81 +  //The above test could also be coded like this:
    2.82 +  check(kruskal(G,
    2.83 +		makeKruskalMapInput(G, edge_cost_map),
    2.84 +		makeKruskalSequenceOutput(back_inserter(tree_edge_vec)))
    2.85 +	==-31,
    2.86 +	"Total cost should be -31.");
    2.87 +
    2.88 +  check(tree_edge_vec.size()==5,"The tree should have 5 edges.");
    2.89 +
    2.90 +  check(tree_edge_vec[0]==e1 &&
    2.91 +	tree_edge_vec[1]==e2 &&
    2.92 +	tree_edge_vec[2]==e5 &&
    2.93 +	tree_edge_vec[3]==e7 &&
    2.94 +	tree_edge_vec[4]==e9,
    2.95 +	"Wrong tree.");
    2.96 +*/
    2.97 +  return 0;
    2.98 +}