Excellent, that does exactly what I need!
I had implemented my own version of this in Java (VF2 algorithm) which
literally takes an hour to do something this does in 5 minutes, even on a
virtual host with only 1 out of 4 cores.
Thanks,
Jelle
On 3 January 2013 22:37, Tiago Peixoto [via Main discussion list for the
graph-tool project] <[email protected]> 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]<http://user/SendEmail.jtp?type=node&node=4024894&i=0>>
>
>
>
> _______________________________________________
> graph-tool mailing list
> [hidden email] <http://user/SendEmail.jtp?type=node&node=4024894&i=1>
> http://lists.skewed.de/mailman/listinfo/graph-tool
>
> *signature.asc* (565 bytes) Download
> Attachment<http://main-discussion-list-for-the-graph-tool-project.982480.n3.nabble.com/attachment/4024894/0/signature.asc>
> --
> Tiago de Paula Peixoto <[email protected]>
>
>
> ------------------------------
> 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<http://main-discussion-list-for-the-graph-tool-project.982480.n3.nabble.com/template/NamlServlet.jtp?macro=unsubscribe_by_code&node=4024889&code=amVsbGUudmVyYWFAa2Utd29ya3MuY29tfDQwMjQ4ODl8MTk0ODgyODA5>
> .
> NAML<http://main-discussion-list-for-the-graph-tool-project.982480.n3.nabble.com/template/NamlServlet.jtp?macro=macro_viewer&id=instant_html%21nabble%3Aemail.naml&base=nabble.naml.namespaces.BasicNamespace-nabble.view.web.template.NabbleNamespace-nabble.view.web.template.NodeNamespace&breadcrumbs=notify_subscribers%21nabble%3Aemail.naml-instant_emails%21nabble%3Aemail.naml-send_instant_email%21nabble%3Aemail.naml>
>
--
View this message in context:
http://main-discussion-list-for-the-graph-tool-project.982480.n3.nabble.com/Error-installing-graph-tool-on-windows-tp4024889p4024895.html
Sent from the Main discussion list for the graph-tool project mailing list
archive at Nabble.com._______________________________________________
graph-tool mailing list
[email protected]
http://lists.skewed.de/mailman/listinfo/graph-tool
