Some modification on the undirected graph interface.
Doc improvments
3 #include <lemon/smart_graph.h>
4 #include <lemon/bin_heap.h>
5 #include <lemon/graph_reader.h>
6 #include <lemon/graph_to_eps.h>
13 using namespace lemon;
15 int main(int argc, char *argv[])
19 std::cerr << "USAGE: coloring input_file.lgf" << std::endl;
20 std::cerr << "The file 'input_file.lgf' has to contain a graph in LEMON format together with a nodemap called 'coords' to draw the graph (e.g. sample.lgf is not such a file)." << std::endl;
25 //input stream to read the graph from
26 std::ifstream is(argv[1]);
28 typedef UndirSmartGraph Graph;
29 typedef Graph::Node Node;
30 typedef Graph::NodeIt NodeIt;
31 typedef Graph::UndirEdge UndirEdge;
32 typedef Graph::IncEdgeIt IncEdgeIt;
36 UndirGraphReader<Graph> reader(is, graph);
37 Graph::NodeMap<xy<double> > coords(graph);
38 reader.readNodeMap("coords", coords);
42 Graph::NodeMap<int> color(graph, -2);
44 Graph::NodeMap<int> heapMap(graph, -1);
45 BinHeap<Node, int, Graph::NodeMap<int> > heap(heapMap);
47 for (NodeIt it(graph); it != INVALID; ++it) {
48 heap.push(it, countOutEdges(graph, it));
53 while (!heap.empty()) {
54 Node node = heap.top();
57 order.push_back(node);
58 for (IncEdgeIt it(graph, node); it != INVALID; ++it) {
59 Node target = graph.runningNode(it);
60 if (color[target] == -2) {
61 heap.decrease(target, heap[target] - 1);
66 for (int i = order.size() - 1; i >= 0; --i) {
68 for (IncEdgeIt it(graph, order[i]); it != INVALID; ++it) {
69 Node target = graph.runningNode(it);
70 if (color[target] != -1) {
71 forbidden.insert(color[target]);
75 while (forbidden.find(current) != forbidden.end()) ++current;
76 color[order[i]] = current;
81 graphToEps(graph, "six_coloring.eps").
82 title("Six Colored Graph").copyright("(C) 2005 LEMON Project").
83 coords(coords).nodeColors(composeMap(colorSet, color)).