On 3 January 2013 22:37, Tiago Peixoto [via Main discussion list for the graph-tool project] <[hidden email]> wrote:

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 <[hidden email]>

_______________________________________________
graph-tool mailing list
[hidden email]
http://lists.skewed.de/mailman/listinfo/graph-tool

signature.asc (565 bytes) Download Attachment

--
Tiago de Paula Peixoto <[hidden email]>

If you reply to this email, your message will be added to the discussion below:

http://main-discussion-list-for-the-graph-tool-project.982480.n3.nabble.com/Error-installing-graph-tool-on-windows-tp4024889p4024894.html

To unsubscribe from Error installing graph-tool on windows, click here.
NAML