1 #ifndef __MINLCA_UTILS_GRAPH_UTILS_H
2 #define __MINLCA_UTILS_GRAPH_UTILS_H
4 #include <lemon/core.h>
5 #include <lemon/smart_graph.h>
6 #include <lemon/random.h>
7 #include <lemon/dim2.h>
30 template<
typename IS,
typename Graph>
38 using namespace lemon;
39 TEMPLATE_GRAPH_TYPEDEFS(Graph);
42 in >> aux >> aux >> n >> m;
47 vector<Node> vertices;
50 for (
int i = 0; i < n; ++i) {
51 vertices.push_back(g.addNode());
57 for (
int i = 0; i < n; ++i) {
58 swap(vertices[i], vertices[r.integer(i, n)]);
65 g.addEdge(vertices[u - 1], vertices[v - 1]);
76 template<
typename IS,
typename Graph>
84 using namespace lemon;
85 TEMPLATE_GRAPH_TYPEDEFS(Graph);
92 vector<Node> vertices;
95 vector<int> degrees(n, 0);
97 for (
int i = 0; i < n; ++i) {
98 vertices.push_back(g.addNode());
105 for (
int i = 0; i < n; ++i) {
106 swap(vertices[i], vertices[r.integer(i, n)]);
110 for (
int u = 0; u < n; ++u) {
111 for (
int i = 0; i < degrees[u]; ++i) {
115 if (findEdge(g, vertices[u], vertices[v]) == INVALID) {
116 g.addEdge(vertices[u], vertices[v]);
130 template<
typename IS = std::istream,
typename Graph = lemon::SmartGraph>
159 template<
typename IS = std::istream,
typename Graph = lemon::SmartGraph>
170 template<
typename Graph>
173 const typename Graph::Node &v
176 return lemon::countIncEdges(g, v);
180 template<
typename Graph>
185 using namespace lemon;
186 TEMPLATE_GRAPH_TYPEDEFS(Graph);
189 for (NodeIt v(g); v != INVALID; ++v) {
190 deg = std::max(deg,
degree(g, v));
GraphFormat
Available graph formats.
void readGraphRmfRandomOrder(Graph &g, int seed, IS &in)
Read a graph in RMF format.
void readGraph(Graph &g, GraphFormat f=RMF, IS &in=std::cin)
Read a graph.
void readGraphGraRandomOrder(Graph &g, int seed, IS &in)
Read a graph in GRA format.
Default namespace Default namespace for MinLCA algorithms.
int degree(const Graph &g, const typename Graph::Node &v)
Degree of a vertex.
void readGraphRandomOrder(Graph &g, int seed=0, GraphFormat f=RMF, IS &in=std::cin)
Read a graph in random order.
int maxDegree(const Graph &g)
Maximum degree of a graph.