Ask Your Question

Enumerate isomrphic subgraphs of graph vertex labeled

asked 2010-09-14 19:17:45 -0500

sriram gravatar image

updated 2011-04-28 09:25:38 -0500

Kelvin Li gravatar image

Enumerate all isomorphic subgraphs of given graph given the subgraph adjacency matrix

edit retag flag offensive close merge delete


Can you post your code (up until the computation you want to perform)?

ccanonc gravatar imageccanonc ( 2010-09-17 10:28:52 -0500 )edit

1 answer

Sort by ยป oldest newest most voted

answered 2011-06-02 23:59:46 -0500

staffan gravatar image

All graphs in Sage support iteration over its major subcomponents, at least vertices and to create a graph from its adjacency matrix

mg= Graph(adj) mg.is_isomorphic(mg) -> True

# graph from adjency matrix
adj= Matrix ([ [0, 1, 1], [1, 0, 1], [1, 1, 0] ])
mg= Graph(adj)
mg.is_isomorphic(mg) -> True

If are you looking for the isomorphic subgraphs of the one you specify with the adj. graph you can usemg.subgraph_search_iterator().

too see how it might be used here. If you post the source as suggested above we could get a more detailed answer.

Here is a simple example of looking for the simplest graph, with zero vertices:

eg = Graph()
[p for p in mg.subgraph_search_iterator(eg)]
edit flag offensive delete link more

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools


Asked: 2010-09-14 19:17:45 -0500

Seen: 384 times

Last updated: Jun 02 '11