Re: [boost] Newbie question: association graphs

From: Torsten Schindler (Torsten.Schindler_at_[hidden])
Date: 2001-08-06 10:06:12

Hi Jeremy,

First of all many thanks for your help.

> > // 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
> > //
> 
> Could you describe in more detail what the purpose of the association
> graph is and what you would like to see happen with the vertex
> information.
> 
The principle problem I want to solve is:
Given a model graph G = (V,E,\mu,\nu) and an input graph
G_I = (V_I,E_I,\mu_I,\nu_I), find all subgraph isomorphisms from G to
G_I.
If no subgraph isomorphism exists, then find the largest subgraph S of G
such that there exists a subgraph isomorphism from S to G_I.
(My graphs represents triangulated/tesselated molecular surfaces with
several properties for each vertex.)

One way to solve the problem is graph matching by clique detection
in an association graph build up from the model and the input graph.
So each vertex of the association graph denotes a vertex-to-vertex
mapping
from the input graph to the model graph and each edge denotes the 
local compatibility of two mappings. The rules for building the
association
graph are:

1. Vertices of the association graph:
   Each mapping of a vertex of graph G to a vertex of graph G_I,
   where the vertices have the same color, creates a new vertex
   of the assocation graph.
2. Edges of the association graph:
   The set of edges in the association graph E_A consists of all edges
   e_A = (v_A,v'_A) with the vertex v_A = (v,v_I), representing a
mapping
   from v to v_I, and with the vertex v'_A = (v',v_I) such that
   (a) v not equal to v' and v_I not equal to v'_I
       (this condition avoids multiple mappings of the same vertex.)
   (b) if there is no edge (v,v') element of the set of the edges E of
       the model graph then there must be no edge (v_I,v'_I) element of
       the set of the edges E_I of the input graph.
   (c) if there is an edge e = (v,v') element of E then there must
       be an edge e_I = (v_I,v'_I).

As you can see in my implementation of these rules in
build_association_graph
I add a vertex to the association graph if condition 1. is fullfilled
and than this new vertex is connected to the other vertices, which are
already 
added to the association graph, if condition 2. is fullfilled.

With my first comment I mean that the vertex information should be
stored
in an interior OR in an exterior property map depending on the user
of the association graph.

My second comment is much more important. I have two other algorithms
for clique detection, where the speed of the algorithms is
improved a little bit if the vertices of the association graph are
sorted after decreasing edge density (# of adjacent vertices of an
vertex),
i.e. in pseudo code:
   vector<int> edge_histogram(num_vertices(G_A),0);
   for_each vertex of G_A count adjacent vertices and fill
edge_histogram.
   sort vertices and corresponding edges in G_A after decreasing numbers
in
   edge_histogram.

>From the implementation of the Bron/Kerbosch algorithm you can see
in the member function DetectClique::extend that this (pre-)sorting is
not
needed, because the algorithm always determines the vertex with the
minimum
number of disconnections during the clique search.

For the clique detection I want something like a finite state machine
that returns first the maximum clique(s) than the next smaller clique(s)
and so on. But I have never written a finite state machine, thus I don't
know how to reformulate the Bron/Kerbosch-algorithm as a state machine.
Any hints?

Ciao,

Torsten