1 | #include <vector> |
---|

2 | |
---|

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> |
---|

7 | |
---|

8 | using namespace std; |
---|

9 | using namespace lemon; |
---|

10 | |
---|

11 | int main() { |
---|

12 | typedef UndirSmartGraph Graph; |
---|

13 | typedef Graph::Node Node; |
---|

14 | typedef Graph::NodeIt NodeIt; |
---|

15 | typedef Graph::UndirEdge UndirEdge; |
---|

16 | typedef Graph::IncEdgeIt IncEdgeIt; |
---|

17 | |
---|

18 | Graph graph; |
---|

19 | |
---|

20 | UndirGraphReader<Graph> reader(std::cin, graph); |
---|

21 | Graph::NodeMap<xy<double> > coords(graph); |
---|

22 | reader.readNodeMap("coords", coords); |
---|

23 | |
---|

24 | reader.run(); |
---|

25 | |
---|

26 | Graph::NodeMap<int> color(graph, -2); |
---|

27 | |
---|

28 | Graph::NodeMap<int> heapMap(graph, -1); |
---|

29 | BinHeap<Node, int, Graph::NodeMap<int> > heap(heapMap); |
---|

30 | |
---|

31 | for (NodeIt it(graph); it != INVALID; ++it) { |
---|

32 | heap.push(it, countOutEdges(graph, it)); |
---|

33 | } |
---|

34 | |
---|

35 | vector<Node> order; |
---|

36 | |
---|

37 | while (!heap.empty()) { |
---|

38 | Node node = heap.top(); |
---|

39 | heap.pop(); |
---|

40 | color[node] = -1; |
---|

41 | order.push_back(node); |
---|

42 | for (IncEdgeIt it(graph, node); it != INVALID; ++it) { |
---|

43 | Node target = graph.runningNode(it); |
---|

44 | if (color[target] == -2) { |
---|

45 | heap.decrease(target, heap[target] - 1); |
---|

46 | } |
---|

47 | } |
---|

48 | } |
---|

49 | |
---|

50 | for (int i = order.size() - 1; i >= 0; --i) { |
---|

51 | set<int> forbidden; |
---|

52 | for (IncEdgeIt it(graph, order[i]); it != INVALID; ++it) { |
---|

53 | Node target = graph.runningNode(it); |
---|

54 | if (color[target] != -1) { |
---|

55 | forbidden.insert(color[target]); |
---|

56 | } |
---|

57 | } |
---|

58 | int current = 0; |
---|

59 | while (forbidden.find(current) != forbidden.end()) ++current; |
---|

60 | color[order[i]] = current; |
---|

61 | } |
---|

62 | |
---|

63 | ColorSet colorSet; |
---|

64 | |
---|

65 | graphToEps(graph, "six_coloring.eps"). |
---|

66 | title("Six Colored Graph").copyright("(C) 2005 LEMON Project"). |
---|

67 | coords(coords).nodeColors(composeMap(colorSet, color)). |
---|

68 | scaleToA4().run(); |
---|

69 | |
---|

70 | return 0; |
---|

71 | } |
---|