Boost logo

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