equal
deleted
inserted
replaced
12 * express or implied, and with no claim as to its suitability for any |
12 * express or implied, and with no claim as to its suitability for any |
13 * purpose. |
13 * purpose. |
14 * |
14 * |
15 */ |
15 */ |
16 |
16 |
|
17 ///\ingroup demos |
|
18 ///\file |
|
19 ///\brief Coloring of a graph. |
|
20 /// |
|
21 /// This example shows how can we color the nodes of a plan graph efficiently |
|
22 /// with six colors. |
|
23 /// |
|
24 /// \include coloring.cc |
|
25 |
17 #include <vector> |
26 #include <vector> |
18 |
27 |
|
28 #include <iostream> |
|
29 |
19 #include <lemon/smart_graph.h> |
30 #include <lemon/smart_graph.h> |
20 #include <lemon/bin_heap.h> |
31 #include <lemon/linear_heap.h> |
21 #include <lemon/graph_reader.h> |
32 #include <lemon/graph_reader.h> |
22 #include <lemon/graph_to_eps.h> |
33 #include <lemon/graph_to_eps.h> |
23 |
34 |
24 #include <fstream> |
35 #include <fstream> |
25 #include <iostream> |
|
26 |
36 |
27 |
37 |
28 using namespace std; |
38 using namespace std; |
29 using namespace lemon; |
39 using namespace lemon; |
30 |
40 |
49 reader.run(); |
59 reader.run(); |
50 |
60 |
51 Graph::NodeMap<int> color(graph, -2); |
61 Graph::NodeMap<int> color(graph, -2); |
52 |
62 |
53 Graph::NodeMap<int> heapMap(graph, -1); |
63 Graph::NodeMap<int> heapMap(graph, -1); |
54 BinHeap<Node, int, Graph::NodeMap<int> > heap(heapMap); |
64 LinearHeap<Node, Graph::NodeMap<int> > heap(heapMap); |
55 |
65 |
56 for (NodeIt it(graph); it != INVALID; ++it) { |
66 for (NodeIt it(graph); it != INVALID; ++it) { |
57 heap.push(it, countOutEdges(graph, it)); |
67 heap.push(it, countOutEdges(graph, it)); |
58 } |
68 } |
59 |
69 |