Re: [igraph] Extensions to colored graph isomorphism

[Gábor Csárdi]

Geoff,

you can encode all the vertex attribute requirements into a vertex 'color'.
I can add the edge colors. (https://bugs.launchpad.net/igraph/+bug/360375)

Best,
Gabor

On Mon, Apr 13, 2009 at 2:32 AM, Geoff Oxberry <address@hidden> wrote:
> Gabor,
>
> I ran across your library while doing some research on implementations of
> graph data structure libraries for a computational chemistry package. One of
> the core algorithms the package needs is an efficient algorithm that checks
> for colored graph isomorphism, taking into account both node "colors" (each
> node has multiple "colors" associated with it; nodes in our graphs
> correspond to atoms, so one attribute of a node would describe the type of
> atom, like carbon, hydrogen, etc., another attribute of a node would
> describe the electronic state of the node, and so on) and edge "colors"
> (each edge describes the type of bond between atoms, such as a single,
> double, or triple bond). Right now, we're using a naive depth-first search
> algorithm to carry out this task, but it seems like the VF2 algorithm would
> be more efficient. I noticed that your implementation of the VF2 algorithm
> compared node colorings for a single node attribute in each graph. Would it
> be possible to extend this to multiple node and edge attributes as well?
>
> Thanks,
>
> Geoff
>
> --
> Geoffrey Oxberry, E.I.T.
> Ph.D. Candidate, Barton and Green Groups
> Massachusetts Institute of Technology
> Department of Chemical Engineering
> Room 66-363
> 77 Massachusetts Avenue
> Cambridge, MA, USA 02139-4307
> Office: +1 617 253 6468
> E-mail: address@hidden
> Alternate e-mail: address@hidden
>
> "Display of superior knowledge is as great a vulgarity as display of
> superior wealth — greater indeed, inasmuch as knowledge should tend more
> definitely than wealth towards discretion and good manners." — Henry W.
> Fowler
>
> _______________________________________________
> igraph-help mailing list
> address@hidden
> http://lists.nongnu.org/mailman/listinfo/igraph-help
>
>



-- 
Gabor Csardi <address@hidden>     UNIL DGM