|
|
Boost : |
From: Torsten Schindler (Torsten.Schindler_at_[hidden])
Date: 2001-08-03 05:07:52
Hi all,
I need some help to redesign, improve, make my little
program faster. And I want to learn more about designing
algorithms.
It is my first trial with the BOOST graph library,
so please be patient if you read the code I have attached
to that e-mail together with a makefile and an file for platform
configuration included from the makefile from the directory ./MKINCLUDE/
Before you use the makefile and IRIX64.mk adapt it for your
needs, i.e. change the paths indicated by <...>.
If you want the corresponding Linux.mk or OSF1.mk files than send my
an e-mail.
The first thing I want to improve is the way I create my association
graph, than I want to build in error/exception handling.
I place my question and what I imagine in the TODO/COMMENT sections
of the source code.
Thanks for your suggestions and help,
Torsten
//
// This program is still under development!!!
//
// Task of the program:
// Find ALL subgraph isomorphisms of two given graphs
//
#include <boost/config.hpp>
#include <cstdio>
#include <unistd.h>
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <string>
#include <fstream>
#include <sstream>
#include <algorithm>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/adjacency_matrix.hpp>
#include <boost/property_map.hpp>
using namespace std;
using namespace boost;
//---------------------------------------------------------------------------------------
// Coordinates as a new vertex property
enum vertex_coordinates_t { vertex_coordinates = 300 };
namespace boost {
BOOST_INSTALL_PROPERTY(vertex, coordinates);
}
//---------------------------------------------------------------------------------------
// Class to detect cliques with the Bron-Kerbosch algorithm
//
// LITERATURE:
// Bron-Kerbosch maximal clique algorithm from Algorithm 457
// of the Collected Algorithms from CACM
// Available under: http://www.netlib.org/tomspdf/457.pdf
//
// TODO or better "What I want":
// - The detection of the cliques should work like a state machine
// - A clique is a subgraph of a given graph, thus the
// clique detector should deliver subgraphs representing the
cliques
//
template <class Graph>
class DetectClique
{
public:
// Constructor
DetectClique(const Graph& graph, int max_, bool check_) : G(graph),
max_count(max_),
check_max(check_) {};
// Methode to start the clique detection
void start_detection() {
reached_max_count = false;
count = 0;
Cmax = 0;
int N = num_vertices(G);
// Initialize the array 'all'
vector<int> all; // 1..N
all.reserve(N);
for (int i = 0; i < N; i++) {
all.push_back(i);
}
extend(all, 0, N);
}
// Get all maximal cliques of graph G
vector<vector<int> > get_max_cliques() {
return Cliques;
}
private:
// Check if two vertices are connected
bool is_connected(int a, int b) {
// In the Bron/Kerbosch Algorithm identical
// vertices are connected!!!
if (a == b) {
return true;
}
// Check if connection between vertex a and b exists
if ((edge(a,b,G)).second) {
return true;
}
return false;
}
// Recursive extension of a clique
void extend(vector<int> old_set, int ne, int ce) {
if (reached_max_count) {
return;
}
int fixp = 0;
int s;
int minnod = ce;
int nod = 0;
// Determine each counter value and look for minimum
for (int i = 0; i < ce && minnod != 0; i++) {
int p = old_set[i];
int count = 0;
int pos;
// Count disconnections of the vertices
for (int j = ne; j < ce && count < minnod; j++) {
if (!is_connected(p,old_set[j])) {
count++;
// Save position of potential candidate
pos = j;
}
}
// Test new minimum
if (count < minnod) {
minnod = count;
fixp = p;
if (i < ne) {
s = pos;
} else {
s = i;
// Preincrement nod
nod = 1;
}
}
}
// If fixed point initially chosen from 'candidates' then
// number of disconnections will be preincreased by one
// Backtrackcycle
for (nod += minnod; nod >= 1; nod--) {
// Interchange
int p = old_set[s];
old_set[s] = old_set[ne];
old_set[ne] = p;
int sel = old_set[ne];
// Fill new set 'not'
vector<int> new_set; // 1..ce
new_set.reserve(ce);
int new_ne = 0;
for (int i = 0; i < ne; i++) {
if (is_connected(sel,old_set[i])) {
new_set.push_back(old_set[i]);
new_ne++;
}
}
// Fill new set 'candidates'
int new_ce = new_ne;
for (int i = ne + 1; i < ce; i++) {
if (is_connected(sel,old_set[i])) {
new_set.push_back(old_set[i]);
new_ce++;
}
}
// Add to 'complete_subgraph'
complete_subgraph.push_back(sel);
if (new_ce == 0) {
//------------------------------------------
// Handle found clique
count++;
if (complete_subgraph.size() > Cmax) { // New maximal
clique found
Cmax = complete_subgraph.size();
Cliques.clear();
Cliques.push_back(complete_subgraph);
} else if (complete_subgraph.size() == Cmax) {
// Clique with equal size of old clique found
Cliques.push_back(complete_subgraph);
}
// Number of maximum iterations exceeded
if (check_max && count >= max_count) {
reached_max_count = true;
return;
}
} else {
if (new_ne < new_ce) {
extend(new_set, new_ne, new_ce);
}
}
// Remove vertex from 'complete_subgraph'
complete_subgraph.pop_back();
// Add to 'not'
ne++;
// Select a candidate disconnected to the fixed point
if (nod > 1) {
s = ne;
while (is_connected(fixp,old_set[s])) {
s++;
}
}
} // end of backtrackcycle
}
// Vector which contains the actual clique
vector<int> complete_subgraph; // behaves like a stack
// Graph to detect cliques
const Graph& G;
bool reached_max_count; // Flag to signal if the maximal count
is
reached
int Cmax; // Size of maximum clique
int count; // Clique counter
int max_count; // Maximum number of cliques to detect
bool check_max; // Check for a maximum number if
check_max is true
vector<vector<int> > Cliques; // Cliques with maximum number of
vertices
};
//---------------------------------------------------------------------------------------
// Class to check if vertices/or edges are equal
// Should become a real visitor
template <class Graph>
struct property_equal
{
// ctor
property_equal(const Graph& g1_, const Graph& g2_) : g1(g1_),
g2(g2_) {
}
// Check if to vertices are equal
template <class Vertex>
bool vertices(Vertex v1, Vertex v2) const {
return (get(get(vertex_color, g1), v1) == get(get(vertex_color,
g2), v2));
}
// Check if to edges are equal
template <class Edge>
bool edges(Edge e1, Edge e2) const {
return (get(get(edge_weight, g1), e1) == get(get(edge_weight,
g2),
e2));
}
const Graph& g1;
const Graph& g2;
};
//---------------------------------------------------------------------------------------
// Class to check if vertices/or edges are approximately equal (within a
given tolerance)
// Should become a real visitor
//
// TODO:
// - Implement tolerance checking
//
template <class Graph>
struct approximate_equal
{
// ctor
approximate_equal(const Graph& g1_, const Graph& g2_) : g1(g1_),
g2(g2_) { }
// Check if vertices have approximately the same properties
template <class Vertex>
bool vertices(Vertex v1, Vertex v2) const {
typename property_map<Graph, vertex_color_t>::const_type
vertex_color_map1 = get(vertex_color,g1);
typename property_map<Graph, vertex_color_t>::const_type
vertex_color_map2 = get(vertex_color,g2);
return (vertex_color_map1[v1] == vertex_color_map2[v2]);
}
// Check if edges have approximately the same properties
template <class Edge>
bool edges(Edge e1, Edge e2) const {
typename property_map<Graph, edge_weight_t>::const_type
edge_weight_map1 = get(edge_weight,g1);
typename property_map<Graph, edge_weight_t>::const_type
edge_weight_map2 = get(edge_weight,g2);
return (edge_weight_map1[e1] == edge_weight_map2[e2]);
}
const Graph& g1;
const Graph& g2;
};
//---------------------------------------------------------------------------------------
// Count the vertices of the resulting association graph
// to be able to create an adjacency matrix to use faster
// access for connectivity information
template <class Graph, class Comparer>
int count_vertices(const Graph& G, const Graph& GI, Comparer compare)
{
int counter = 0;
graph_traits<Graph>::vertex_iterator vi, viend, vj, vjend;
for (tie(vi,viend) = vertices(G); vi != viend; ++vi) {
for (tie(vj,vjend) = vertices(GI); vj != vjend; ++vj) {
if (compare.vertices(*vi,*vj)) {
++counter;
}
}
}
return counter;
}
//---------------------------------------------------------------------------------------
// Create a new association graph from two given graphs
// COMMENTS:
// - Building up the association graph should be more flexible,
// i.e. the user should have the possibility to store
// the vertex information of the two given graphs
// or to leave it away
// - Presorting or sorting the vertices of the association
// graph after edge density
//
template <class Graph, class AssociationGraph, class Comparer>
void build_association_graph(const Graph& G, const Graph& GI,
AssociationGraph& GA,
Comparer compare)
{
property_map<AssociationGraph, vertex_color_t>::type ass_map =
get(vertex_color, GA);
graph_traits<Graph>::vertex_iterator vi, viend, vj, vjend;
graph_traits<AssociationGraph>::vertex_descriptor new_vertex;
// For all vertices in graph G
for (tie(vi,viend) = vertices(G); vi != viend; ++vi) {
// For all vertices in graph GI
for (tie(vj,vjend) = vertices(GI); vj != vjend; ++vj) {
if (compare.vertices(*vi,*vj)) {
// Add vertex if color of graph G equals color of graph
GI
new_vertex = add_vertex(GA);
put(ass_map, new_vertex, make_pair(*vi,*vj));
// Connect new vertex with the previously added vertices
// of the association graph
graph_traits<AssociationGraph>::vertex_iterator via,
vend;
for (tie(via,vend) = vertices(GA); via != vend - 1;
++via)
{
graph_traits<Graph>::vertex_descriptor v1,v2,
vi1,vi2;
v1 = vertex((ass_map[*via]).first,GA);
v2 = vertex(*vi,GA);
vi1 = vertex((ass_map[*via]).second,GA);
vi2 = vertex(*vj,GA);
// If we have no multiple mapping
if (v1 != v2 && vi1 != vi2) {
graph_traits<Graph>::edge_descriptor e, ei;
bool has_edge_e, has_edge_ei;
tie(e, has_edge_e) = edge(v1, v2, G);
tie(ei, has_edge_ei) = edge(vi1, vi2, GI);
// If there is an e = (v,v') of E then there
must
be
// an edge ei = (vi,vi') of EI with the same
color
OR
// if there is no e = (v,v') of E then there
must
be
// no edge ei = (vi,vi') of EI
if ((!has_edge_e && !has_edge_ei) ||
(has_edge_e && has_edge_ei &&
compare.edges(e,ei))) {
add_edge(*via, new_vertex, GA);
}
}
}
}
}
}
}
//---------------------------------------------------------------------------------------
// Functor to print coordinate information of the vertices
template <class Graph>
struct coordinates_printer
{
coordinates_printer(Graph& g, ostream& os) : G(g), m_os(os) {}
typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
void operator()(Vertex c) const {
typename boost::property_map<Graph,vertex_index_t>::type
index_map = get(vertex_index, G);
typename boost::property_map<Graph,vertex_coordinates_t>::type
xyz_map = get(vertex_coordinates, G);
m_os << setw(6) << index_map[c] << " ";
typedef vector<double>::const_iterator VD;
for (VD vd = xyz_map[c].begin(); vd != xyz_map[c].end(); ++vd) {
m_os << setw(5) << *vd << " ";
}
m_os << endl;
}
Graph& G;
ostream& m_os;
};
//---------------------------------------------------------------------------------------
// Simple function to read an input graph
// Format for vertices:
// v #x #y #z #property
// Format for edges:
// e #vertex1 #vertex2 #property
//
// TODO:
// - Should become a class to read graphs with the given format
// - Should have a DIMACS compatible format
//
template <class Graph>
void read_graph(ifstream& file, Graph& Ginput)
{
typedef graph_traits<Graph>::vertex_descriptor Vertex;
typedef property<edge_weight_t, int> EdgeProperty;
typedef typename property_map<Graph, vertex_color_t>::type
VertexColorMap;
VertexColorMap VertexColorG = get(vertex_color, Ginput);
typedef typename property_map<Graph, vertex_coordinates_t>::type
VertexCoordinatesMap;
VertexCoordinatesMap VertexCoordinatesG = get(vertex_coordinates,
Ginput);
char line_buffer[100];
char marker;
while (file.getline(line_buffer,100)) {
istringstream string_buffer(line_buffer);
string_buffer >> marker;
if (marker == 'v') {
// Add new vertex to graph Ginput
Vertex v;
v = add_vertex(Ginput);
// Assign property to vertex
vector<double> xyz(3);
int vcolor;
string_buffer >> xyz[0] >> xyz[1] >> xyz[2] >> vcolor;
put(VertexColorG, v, vcolor);
put(VertexCoordinatesG, v, xyz);
} else if (marker == 'e') {
// Add new edge to model graph G
int vertex1, vertex2, edge_property;
string_buffer >> vertex1 >> vertex2 >> edge_property;
add_edge(vertex1, vertex2,
EdgeProperty(edge_property),Ginput);
}
}
}
//---------------------------------------------------------------------------------------
// A little program to build up an association graph from two given
// graphs and detect all cliques in the association graph.
// Finally we get all subgraph isomorphisms (not only the exact subgraph
isomorphism
// as with the Ullmann algorithm) between the two given graphs.
int main(int argc, char *argv[])
{
//-------------------------
// Process the command line
extern char *optarg;
extern int optind;
string model_graph; // Name of the file which contains the model
graph
string input_graph; // Name of the file which contains the input
graph
bool error_flag = false;
int c;
int iterations = 10; // Default value
bool check_for_max = false;
while ((c = getopt(argc, argv, "n:i:m:")) != -1) {
char buffer[200];
int int_buffer;
switch(c) {
case 'n':
if (!sscanf(optarg, "%d", &int_buffer)) {
error_flag = true;
break;
}
iterations = int_buffer;
cout << "# Number of iterations: " << iterations << endl;
check_for_max = true;
break;
case 'i':
if (!sscanf(optarg, "%s", buffer)) {
error_flag = true;
break;
}
input_graph = buffer;
cout << "# File with input graph: " << input_graph << endl;
break;
case 'm':
if (!sscanf(optarg, "%s", buffer)) {
error_flag = true;
break;
}
model_graph = buffer;
cout << "# File with model graph: " << model_graph << endl;
break;
case '?':
error_flag = true;
}
}
// Check command line for errors.
if (error_flag) {
cerr << "Usage: " << argv[0]
<<" -i <input graph file> -m <model graph file> -n <number
of
max. iterations>" << endl;
exit(1);
}
if ((argc - optind != 0) || (argc < 4)) {
cerr << "Too few arguments given!" << endl;
cerr << "Usage: " << argv[0]
<<" -i <input graph file> -m <model graph file> -n <number
of
max. iterations>" << endl;
exit(1);
}
//-----------------------------
// Define property types
typedef property<vertex_coordinates_t, vector<double> >
VertexCoordinates;
typedef property<vertex_color_t, int, VertexCoordinates>
VertexColor;
typedef property<vertex_index_t, int, VertexColor> VertexProperty;
typedef property<edge_weight_t, int> EdgeProperty;
// Define graph type
typedef adjacency_list<vecS, vecS, undirectedS, VertexProperty,
EdgeProperty > Graph;
// Define required property type maps
typedef property_map<Graph, vertex_index_t>::type VertexIndexMap;
typedef property_map<Graph, vertex_color_t>::type VertexColorMap;
typedef property_map<Graph, vertex_coordinates_t>::type
VertexCoordinatesMap;
typedef property_map<Graph, edge_weight_t>::type EdgeColorMap;
// Define type of vertex and edge for that kind of graph
typedef graph_traits<Graph>::vertex_descriptor Vertex;
typedef graph_traits<Graph>::edge_descriptor Edge;
//-----------------------------
// Create model and input graph
Graph G, GI;
// Create property maps
VertexIndexMap G_index_map = get(vertex_index, G);
VertexColorMap G_vertex_map = get(vertex_color, G);
VertexCoordinatesMap G_coordinates_map = get(vertex_coordinates, G);
VertexIndexMap GI_index_map = get(vertex_index, GI);
VertexColorMap GI_vertex_map = get(vertex_color, GI);
VertexCoordinatesMap GI_coordinates_map = get(vertex_coordinates,
GI);
//--------------------
// Read model graph G
ifstream model_graph_stream(model_graph.c_str());
if (!model_graph_stream) {
cerr << "Model graph file: " << input_graph << " not found" <<
endl;
exit(1);
}
read_graph(model_graph_stream,G);
cout << "# Model graph G" << endl;
cout << "# Number of vertices in the model Graph: " <<
num_vertices(G)
<< endl;
cout << "# Number of edges in the model Graph: " << num_edges(G)
<<
endl;
// cout << "# G_index_map:" << endl;
// print_graph(G, G_index_map);
// cout << "# G_vertex_map:" << endl;
// print_graph(G, G_vertex_map);
// cout << endl;
// cout << "# Coordinates of the vertices of graph G" << endl;
// for_each(vertices(G).first, vertices(G).second,
// coordinates_printer<Graph>(G,cout));
// cout << endl;
//--------------------
// Read input graph GI
ifstream input_graph_stream(input_graph.c_str());
if (!input_graph_stream) {
cerr << "Input graph file: " << input_graph << " not found" <<
endl;
exit(1);
}
read_graph(input_graph_stream,GI);
cout << "# Input graph GI" << endl;
cout << "# Number of vertices in the input Graph: " <<
num_vertices(GI)
<< endl;
cout << "# Number of edges in the input Graph: " << num_edges(GI)
<<
endl;
// cout << "# GI_index_map:" << endl;
// print_graph(GI, GI_index_map);
// cout << "# GI_vertex_map:" << endl;
// print_graph(GI, GI_vertex_map);
// cout << endl;
// cout << "# Coordinates of the vertices of graph GI" << endl;
// for_each(vertices(GI).first, vertices(GI).second,
// coordinates_printer<Graph>(GI,cout));
// cout << endl;
//----------------------------------
// Construct association graph
// Define property types for association graph
typedef property<vertex_color_t, pair<int,int> > VertexPair;
typedef property<vertex_index_t, int, VertexPair> AssVertexProperty;
// Define graph type for association graph: adjacency list
typedef adjacency_list<vecS, vecS, undirectedS, AssVertexProperty,
no_property > AssociationGraph;
// Define graph type for association graph: adjacency matrix
int N = count_vertices(G,GI, approximate_equal<Graph>(G,GI));
cout << "# Precalculated number of vertices in the association
graph: "
<< N << endl;
// typedef adjacency_matrix<undirectedS, AssVertexProperty >
AssociationGraph;
// Create association graph
AssociationGraph GA;
// build_association_graph(G,GI, GA, property_equal<Graph>(G,GI));
cout << "Building association graph..." << endl;
build_association_graph(G,GI, GA, approximate_equal<Graph>(G,GI));
cout << "...finished" << endl;
// print_graph(GA);
cout << "# Number of vertices in the association graph: " <<
num_vertices(GA) << endl;
cout << "# Number of edges in the association graph: " <<
num_edges(GA) << endl;
int a = num_vertices(GA);
int b = (a*(a-1))/2;
cout << "# Maximum number of possible edge in the association graph:
"
<< b << endl;
//----------------------------------------
// Detect cliques in the association graph
cout << "Detecting cliques" << endl;
DetectClique<AssociationGraph>
detector(GA,iterations,check_for_max);
detector.start_detection();
cout << "...finished" << endl;
vector<vector<int> > maximal_cliques = detector.get_max_cliques();
cout << "Maximum common subgraphs:" << endl;
if (maximal_cliques.empty()) {
cout << "No maximal common subgraphs found!" << endl;
return 0;
}
typedef vector<int>::const_iterator VI;
property_map<AssociationGraph, vertex_color_t>::type ass_map =
get(vertex_color, GA);
for (int i = 0; i < maximal_cliques.size(); i++) {
cout <<
"-------------------------------------------------------------------" <<
endl;
cout << "G1: ";
for (int j = 0; j < maximal_cliques[i].size(); j++) {
cout << setw(5) << ass_map[maximal_cliques[i][j]].first <<
"
";
}
cout << endl;
cout << "G2: ";
for (int j = 0; j < maximal_cliques[i].size(); j++) {
cout << setw(5) << ass_map[maximal_cliques[i][j]].second <<
"
";
}
cout << endl;
}
return 0;
}
#------------------------------------------------------------------------
#
# makefile
#
# 1) The BIN_SH enviroment variable must be set to xpg4 on alpha
platforms
# to get POSIX behaviour:
#
# setenv BIN_SH xpg4
#
# 2) The enviroment variable PLATFORM must be initialized with
# uname -s
# e.g. in .login file: set OSNAME = `uname -s`
# setenv PLATFORM $OSNAME
#
# 3) The platform specific part of the makefile is stored
# in the directory ./MKINCLUDE
#
# 4) Object file are stored in ${PLATFORM}_OBJS directories
#
#------------------------------------------------------------------------
SHELL=/bin/sh
# Platform specific stuff
INCMK=MKINCLUDE/${PLATFORM}.mk
include ${INCMK}
# Executable file
EXE_NAME=clique
EXE_PATH=<your path to your own bin directory>/${PLATFORM}
EXE=${EXE_PATH}/${EXE_NAME}
# Source code files
SRCS=association_graph.cpp
# Object files
OBJS=${SRCS:.cpp=.o}
# C++ compiler flags
CC_FLAGS=${INC_PATH} ${CPP_MACROS} ${CC_OPTIONS}
LIBS=${LIB_PATH} ${LIBRARIES}
# Some useful Macros
RM=/bin/rm -f
RMR=/bin/rm -rf
CP=/bin/cp
ECHO=/bin/echo
# Suffix rules
.SUFFIXES: .o .cpp
all: ${EXE}
${EXE}: Makefile ${OBJS}
@${ECHO} "----------------------------------------------------"
@${ECHO} "Recreate dependencies and Makefile with make rebuild"
@${ECHO} "----------------------------------------------------"
@${MAKE} "INCMK=${INCMK}" "CC_FLAGS=${CC_FLAGS}" ${OBJS}
${CC} ${LDFLAGS} -o $@ ${OBJS} ${LIBS}
Makefile:
@${RM} $@
@${CP} makefile $@
@${ECHO} "---------------------"
@${ECHO} "Creating dependencies"
@${ECHO} "---------------------"
@makedepend -f $@ -- ${CC_FLAGS} -- ${SRCS} 2> /dev/null
-@${RM} $@.bak
rebuild: force_rebuild
@${ECHO} "-------------------"
@${ECHO} "Recreating Makefile"
@${ECHO} "-------------------"
@${RM} Makefile
@$(MAKE) Makefile
# Suffix rules
.cpp.o:
${CC} ${CC_FLAGS} -c $< -o $@
# Cleaning section
clean:
-${RM} $(EXE)
-${RM} ${OBJS}
clobber: clean
-${RM} Makefile
realclean: clobber
-${RMR} inc.mk ${RM_FILES}
# Dummy target to force a rebuild
force_rebuild:
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk