The graph adadptors can be alteration observed.
In most cases it uses the adapted graph alteration notifiers.
Only special case is now the UndirGraphAdaptor, where
we have to proxy the signals from the graph.
The SubBidirGraphAdaptor is removed, because it doest not
gives more feature than the EdgeSubGraphAdaptor<UndirGraphAdaptor<Graph>>.
The ResGraphAdaptor is based on this composition.
3 * This file is a part of LEMON, a generic C++ optimization library
5 * Copyright (C) 2003-2006
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
9 * Permission to use, modify and distribute this software is granted
10 * provided that this copyright notice appears in all copies. For
11 * precise terms see the accompanying LICENSE file.
13 * This software is provided "AS IS" with no warranty of any kind,
14 * express or implied, and with no claim as to its suitability for any
21 ///\brief Demonstrating the usage of LEMON's Dijkstra algorithm
23 /// Dijkstra's algorithm computes shortest paths between two nodes in
24 /// a graph with edge lengths. Here we only show some of the
25 /// facilities supplied by our implementation: for the detailed
26 /// documentation of the LEMON Dijkstra class read \ref lemon::Dijkstra "this".
28 /// \include dijkstra_demo.cc
32 #include <lemon/list_graph.h>
33 #include <lemon/dijkstra.h>
35 using namespace lemon;
38 int main (int, char*[])
41 typedef ListGraph Graph;
42 typedef Graph::Node Node;
43 typedef Graph::Edge Edge;
44 typedef Graph::EdgeMap<int> LengthMap;
48 //An example from Ahuja's book
57 Edge s_v2=g.addEdge(s, v2);
58 Edge s_v3=g.addEdge(s, v3);
59 Edge v2_v4=g.addEdge(v2, v4);
60 Edge v2_v5=g.addEdge(v2, v5);
61 Edge v3_v5=g.addEdge(v3, v5);
62 Edge v4_t=g.addEdge(v4, t);
63 Edge v5_t=g.addEdge(v5, t);
75 std::cout << "This program is a simple demo of the LEMON Dijkstra class."
78 "We calculate the shortest path from node s to node t in a graph."
80 std::cout << std::endl;
83 std::cout << "The id of s is " << g.id(s)<< ", the id of t is "
84 << g.id(t) << "." << std::endl;
86 std::cout << "Dijkstra algorithm demo..." << std::endl;
88 Dijkstra<Graph, LengthMap> dijkstra_test(g,len);
92 std::cout << "The distance of node t from node s: "
93 << dijkstra_test.dist(t) << std::endl;
95 std::cout << "The shortest path from s to t goes through the following "
96 << "nodes (the first one is t, the last one is s): "
99 for (Node v=t;v != s; v=dijkstra_test.predNode(v)) {
100 std::cout << g.id(v) << "<-";
103 std::cout << g.id(s) << std::endl;