GeezerVison is showing github.com — boost_graph/example/edge_coloring.cpp at develop · stdgraph/boost_graph

Expand file tree

edge_coloring.cpp

Copy path

More file actions

Latest commit

History

74 lines (65 loc) · 1.88 KB

edge_coloring.cpp

Copy path

File metadata and controls

74 lines (65 loc) · 1.88 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

//=======================================================================

// Authors: Maciej Piechotka

// Distributed under the Boost Software License, Version 1.0. (See

// accompanying file LICENSE_1_0.txt or copy at

// http://www.boost.org/LICENSE_1_0.txt)

//=======================================================================

#include <iostream>

#include <boost/config.hpp>

#include <boost/graph/adjacency_list.hpp>

#include <boost/graph/edge_coloring.hpp>

#include <boost/graph/properties.hpp>

Sample output

Colored using 5 colors

a-d: 4

a-f: 0

b-c: 2

b-e: 3

b-g: 1

b-j: 0

c-d: 0

c-e: 1

d-f: 2

d-i: 1

e-g: 4

f-g: 3

f-h: 1

g-h: 0

int main(int, char*[])

{

using namespace boost;

using namespace std;

using Graph = adjacency_list< vecS, vecS, undirectedS, no_property, size_t,

no_property >;

using Pair = std::pair< std::size_t, std::size_t >;

Pair edges[14] = { Pair(0, 3), // a-d

Pair(0, 5), // a-f

Pair(1, 2), // b-c

Pair(1, 4), // b-e

Pair(1, 6), // b-g

Pair(1, 9), // b-j

Pair(2, 3), // c-d

Pair(2, 4), // c-e

Pair(3, 5), // d-f

Pair(3, 8), // d-i

Pair(4, 6), // e-g

Pair(5, 6), // f-g

Pair(5, 7), // f-h

Pair(6, 7) }; // g-h

Graph G(10);

for (size_t i = 0; i < sizeof(edges) / sizeof(edges[0]); i++)

add_edge(edges[i].first, edges[i].second, G);

size_t colors = edge_coloring(G, get(edge_bundle, G));

cout << "Colored using " << colors << " colors" << endl;

for (size_t i = 0; i < sizeof(edges) / sizeof(edges[0]); i++)

{

cout << " " << (char)('a' + edges[i].first) << "-"

<< (char)('a' + edges[i].second) << ": "

<< G[edge(edges[i].first, edges[i].second, G).first] << endl;

}

return 0;

}