<main procedures>= (U→) [D→]
int
main() {
try { std::cout << find_od(read_graph(std::cin, 0)) << "\n"; }
catch (std::string emsg) {
std::cerr << "! " << emsg << ".\n";
exit(EXIT_FAILURE);
}
}
Definesmain(links are to index).
The solution is straightforward brute force. For that we'll need to keep track of the current solution as well as the best one found so far.
<main procedures>+= (U→) [←D→]
static solution
find_od(const graph & amtx) {
solution current(amtx), best(amtx);
solve(amtx.vertex_count(), current, best);
return best;
}
Definesfind_od(links are to index).
A linear ordering of the vertices of a graph is a permutation of the list 0, 1, ... |V| - 1. A brute-force search is a search of through all permutations of the list.
If the list has v < 2 vertices, then the problem is solved and current
solution can be compared with the best one.
<main procedures>+= (U→) [←D]
static void
solve(unsigned v, solution & current, solution & best) {
if ((--v < 1) ∧ (current.order_distance() < best.order_distance()))
best = current;
else
for (unsigned j = v; 0 < j; j--) {
solve(v, current, best);
current.swap(v, j - 1);
solve(v, current, best);
current.swap(v, j - 1);
}
}
Definessolve(links are to index).
So much for main().
<main.cc>=
#include <iostream>
#include <cstdlib> // for exit() and EXIT_FAILURE
#include "graph.h"
#include "input.h"
#include "solution.h"
// deja vu c++ style
static void solve(unsigned, solution &, solution &);
static solution find_od(const graph &);
<main procedures>
Definesmain.cc(links are to index).
Reading Graphs
For reading use the recursive trick of reading input lines until there's no
more, creating the apropriately sized data structure, then unwind storing each
input line in the data strcture. If an error is detected at any point, bail by
throwing a string error message. The data structure is a graph sized to
contain vcnt vertices.
<read procedures>= (U→) [D→]
graph
read_graph(std::istream & is, unsigned vcnt) {
std::string str;
if (not read_nonblank_string(is, str))
return graph(vcnt + 1);
else {
const naturals neighbors = split_neighbors(str);
const unsigned & vertex = neighbors.get(0);
graph g = read_graph(is, std::max(vcnt, max_vtx(neighbors)));
for (unsigned i = 1; i < neighbors.size(); i++) {
const unsigned & n = neighbors.get(i);
if (vertex == n)
throw std::string("graph contains a self-loop");
g.set_neighbors(vertex, n);
}
return g;
}
}
Definesread_graph(links are to index).
Each non-empty input line should be a node adjacency list:
v n0 n1 ... ni
for i ≥ -1, where v is a vertex and nj is adjacent to v in the graph. All vertices should be numeric labels.
<read procedures>+= (U→) [←D→]
static naturals
split_neighbors(const std::string & str) {
naturals neighbors;
sequence<std::string> pieces;
split_string(str, pieces);
assert(pieces.size() > 0);
for (unsigned i = 0; i < pieces.size(); i++) {
const std::string & piece = pieces.get(i);
if (not check_number(piece))
throw std::string("non-number in input");
neighbors.add(atoi(piece.c_str()));
}
return neighbors;
}
Definessplit_neighbors(links are to index).
<read procedures>+= (U→) [←D]
static unsigned
max_vtx(const naturals & neighbors) {
assert(neighbors.size() > 0);
unsigned max = neighbors.get(0);
for (unsigned i = neighbors.size() - 1; i > 0; i--)
max = std::max(max, neighbors.get(i));
return max;
}
Definesmax_vtx(links are to index).
<input.cc>=
#include "input.h"
#include "utils.h"
// A sequence of non-negative integers.
typedef sequence<unsigned> naturals;
// Deja vu c++ style.
static sequence<unsigned> split_neighbors(const std::string &);
static unsigned max_vtx(const naturals &);
<read procedures>
Definesinput.cc(links are to index).
<input.h>=
#ifndef _input_h_defined_
#define _input_h_defined_
#include <istream>
#include "graph.h"
extern graph read_graph(std::istream &, unsigned);
#endif
Definesinput.h(links are to index).
<solution public methods>= (U→) // Write the given solution to the given output stream. friend std::ostream & operator << (std::ostream &, const solution &); // Return this solution's order distance. unsigned order_distance() const; // Create a new order-difference solution containing the obvious linear // ordering: the ith vertex is in the ith position of the ordering. solution(const graph &); // Swap the vertices at the given order positions in this solution. void swap(unsigned, unsigned);
<solution.cc>=
#include <iostream>
#include "solution.h"
solution & solution::
operator = (const solution & rhs) {
if (this ≠ &rhs) {
delete [] order;
delete [] in_place;
const unsigned vc = rhs.amtx.vertex_count();
order = new unsigned [vc];
in_place = new unsigned [vc];
memcpy(order, rhs.order, sizeof(unsigned)*vc);
memcpy(in_place, rhs.in_place, sizeof(unsigned)*vc);
amtx = rhs.amtx;
}
return *this;
}
std::ostream &
operator << (std::ostream & os, const solution & s) {
// Print the given vertex list to the given output stream.
os << s.order_distance();
for (unsigned i = 0; i < s.amtx.vertex_count(); i++)
os << " " << s.order[i];
return os;
}
unsigned solution::
order_distance() const {
unsigned od = 0;
for (unsigned i = 0; i < amtx.vertex_count(); i++) {
const unsigned here = in_place[i];
for (unsigned j = 0; j < amtx.neighbor_count(i); j++) {
const unsigned n = amtx.get_neighbor(i, j);
if (n > i) {
const unsigned there = in_place[n];
assert(here ≠ there);
od += std::max(here, there) - std::min(here, there) - 1;
}
}
}
return od;
}
solution::
solution(const graph & amtx)
: amtx(amtx), order(new unsigned [amtx.vertex_count()]),
in_place(new unsigned [amtx.vertex_count()]) {
for (unsigned i = 0; i < amtx.vertex_count(); i++) {
order[i] = i;
in_place[i] = i;
}
}
solution::
solution(const solution & s)
: amtx(amtx), order(new unsigned [amtx.vertex_count()]),
in_place(new unsigned [amtx.vertex_count()]) {
memcpy(order, s.order, sizeof(unsigned)*amtx.vertex_count());
memcpy(in_place, s.in_place, sizeof(unsigned)*amtx.vertex_count());
}
solution::
~solution() {
delete [] order;
delete [] in_place;
}
void solution::
swap(unsigned i, unsigned j) {
assert(i ≠ j);
std::swap(in_place[order[i]], in_place[order[j]]);
std::swap(order[i], order[j]);
}
Definessolution.cc(links are to index).
<solution.h>=
#ifndef _solution_h_defined_
#define _solution_h_defined_
#include <ostream>
#include "graph.h"
class solution {
public:
<solution public methods>
// Set this solution equal to the given one.
solution & operator = (const solution &);
// Create a new order-difference solution that's a copy of the given
// solution.
solution(const solution &);
// Get rid of this solution.
~solution();
private:
// The graph of interest.
graph amtx;
// The vertices' linear ordering; order[i] is the vertex in the ith
// position of the ordering.
unsigned * order;
// The inverse of the linear ordering; in_place[i] is vertex i's
// position in the linear ordering.
// Invariant: for all 0 ≤ i < |V| : in_place[order[i]] = i
unsigned * in_place;
};
#endif
Definessolution.h(links are to index).
The Graph
A straightforward representation of an undirected graph.
<graph public methods>= (U→) // Create an graph for the given number of vertices; none of the vertices have // neighbors. graph(unsigned); // Return the jth neighbor of the ith vertex. unsigned get_neighbor(unsigned i, unsigned j) const; // Return the number of nodes adjacent ot the given node. unsigned neighbor_count(unsigned) const; // Indicate that the given vertices are neighbors; die on invalid vertices. void set_neighbors(unsigned, unsigned); // Return the number of vertices in this graph. unsigned vertex_count() const;
Internally, a graph with V vertices is represented as an edge list stored in a V × V - 1 matrix rather than a linked list. The neighbors of vertex i are stored in row i; the number of neighbors are stored in the first element and the neighbors are stored in succeeding elements.
The neighbor matrix is stored as a vector and accessed with the usual matrix-address calcuation:
<graph private methods>= (U→) [D→]
unsigned & graph::
nbrs(unsigned v, unsigned i) const {
assert(v < vertices);
assert(i ≤ vertices);
return neighbors[v*(vertices + 1) + i];
}
Definesnbrs(links are to index).
The first element in the ith neighbor-matrix row is the number of neighbors for vertex i.
<graph private methods>+= (U→) [←D]
unsigned & graph::
ncnt(unsigned v) const {
return nbrs(v, 0);
}
Definesncnt(links are to index).
The rest of the graph ADT is straightforward.
<graph.cc>=
#include <cassert>
#include <cstring>
#include <iostream>
#include "graph.h"
graph::
graph(unsigned size)
: vertices(size), neighbors(new unsigned [size*(size + 1)]) {
for (unsigned i = 0; i < vertices; i++)
ncnt(i) = 0;
}
graph::
graph(const graph & amtx)
: vertices(amtx.vertices),
neighbors(new unsigned [vertices*(vertices + 1)]) {
memcpy(neighbors, amtx.neighbors, sizeof(unsigned)*vertices*(vertices + 1));
}
graph::
~graph() {
delete [] neighbors;
}
unsigned graph::
get_neighbor(unsigned v, unsigned i) const {
assert(ncnt(v) > i);
return nbrs(v, i + 1);
}
<graph private methods>
unsigned graph::
neighbor_count(unsigned v) const {
return ncnt(v);
}
graph & graph::
operator = (const graph & amtx) {
if (this ≠ &amtx) {
vertices = amtx.vertices;
delete [] neighbors;
neighbors = new unsigned [vertices*(vertices + 1)];
memcpy(neighbors, amtx.neighbors, sizeof(unsigned)*vertices*(vertices + 1));
}
return *this;
}
void graph::
print() const {
for (unsigned i = 0; i < vertices*(vertices + 1); i++)
std::cerr << neighbors[i] << " ";
std::cerr << "\n";
}
void graph::
set_neighbors(unsigned v1, unsigned v2) {
setn(v1, v2);
setn(v2, v1);
}
void graph::
setn(unsigned v1, unsigned v2) {
// Set v2 to be v1's neighbor.
for (unsigned i = 1; i ≤ ncnt(v1); i++)
if (v2 == nbrs(v1, i))
return;
nbrs(v1, ++ncnt(v1)) = v2;
}
unsigned graph::
vertex_count() const {
return vertices;
}
#ifdef TESTINGADJACENCYMATRIX
// g++ -o test-am -g -DTESTINGADJACENCYMATRIX graph.cc && ./test-am
int main() {
const unsigned n = 4;
graph a(n);
assert(n == a.vertex_count());
for (unsigned i = 0; i < n; i++)
assert(0 == a.neighbor_count(i));
a.set_neighbors(0, 1);
assert(1 == a.neighbor_count(0));
assert(1 == a.neighbor_count(1));
for (unsigned i = 2; i < n; i++)
assert(0 == a.neighbor_count(i));
a.set_neighbors(1, 0);
a.set_neighbors(0, 1);
a.set_neighbors(1, 0);
a.set_neighbors(0, 1);
}
#endif
Definesgraph.cc(links are to index).
<graph.h>=
#ifndef _graph_h_defined_
#define _graph_h_defined_
class graph {
public:
// Create an graph equal to the given graph.
graph(const graph &);
// Get rid of this graph.
~graph();
// Set this graph equal to the given one.
graph & operator = (const graph &);
<graph public methods>
private:
unsigned vertices;
unsigned * neighbors;
unsigned & nbrs(unsigned, unsigned) const;
unsigned & ncnt(unsigned) const;
void setn(unsigned, unsigned);
void print() const;
};
#endif
Definesgraph.h(links are to index).
graph.cc>: D1
graph.h>: D1
input.cc>: D1
input.h>: D1
main.cc>: D1
solution.cc>: D1
solution.h>: D1