On 01/03/2013 02:36 PM, jcjveraa wrote:
To illustrate what I'd need: in this graph https://www.dropbox.com/s/8nlnqcvhb150utt/example_graph-tool.PNG I for instance want to get all cyclic induced subgraphs with 3 vertices. The algorithm should return [0,1,4], [0,2,4], [2,3,4] and [3,5,6]. Of course it's fine if it finds [4,1,0], [1,0,4] and [4,0,1] and suchlike as well, I can filter easily based on the vertices contained in the subgraph.
If I look for a subgraph with 4 vertices, I want 0 hits because [0,1,2,4] has a chord due to edge [0,4].
Any suggestions on a combination of functions to achieve this would be greatly appreciated :)
This can be done simply as follows, if I understood correctly: from graph_tool.all import * g = Graph(directed=False) g.add_vertex(7) edges = [(5, 6), (5, 3), (6, 3), (3, 4), (3, 2), (4, 2), (4, 0), (4, 1), (2, 0), (1, 0)] for e in edges: g.add_edge(e[0], e[1]) def get_cycle(n): u = Graph(directed=False) u.add_vertex(n) for i in range(n - 1): u.add_edge(i, i + 1) u.add_edge(n - 1, 0) return u S = get_cycle(3) vmaps, emaps = subgraph_isomorphism(S, g) for vm, em in zip(vmaps, emaps): vmask, emask = mark_subgraph(g, S, vm, em) F = Graph(GraphView(g, vfilt=vmask), prune=True) if isomorphism(F, S): print("found: ", vm.a) For this I get: found: [5 6 3] found: [5 3 6] found: [1 4 0] found: [1 0 4] found: [6 5 3] found: [6 3 5] found: [2 4 3] found: [2 4 0] found: [2 3 4] found: [2 0 4] found: [4 1 0] found: [4 2 3] found: [4 2 0] found: [4 3 2] found: [4 0 1] found: [4 0 2] found: [3 5 6] found: [3 6 5] found: [3 2 4] found: [3 4 2] found: [0 1 4] found: [0 2 4] found: [0 4 1] found: [0 4 2] And indeed, if I make S = get_cycle(4), no induced subgraphs are found. Does this help? Cheers, Tiago -- Tiago de Paula Peixoto <tiago@skewed.de>