Hello, Right now, no. My graphs do not have parallel edges.
You are right it is horrible to provide an efficient implementation for labeled subgraph extractions. Just one idea makes my mind busy. I believe what makes the function "subgraph" does not work for labeled graphs is isomorphic checking. while function "g.is_isomorphic" in sage has an argument (called edge_labels) which if it is true then this function checks isomorphism with considering edge labels. Now if in implementation of function "subgraph" we call function "is_isomorphic" with setting the parameter "edge_labels=True", then it should work. What is your opinion? Regards, On Monday, April 27, 2015 at 11:36:07 AM UTC+2, Nathann Cohen wrote: > > Helloooooo, > > Just, how can I search induced subgraphs in labeled graphs? This is the >> main problem. Are there any method or suggestion which helps me to do that? >> > > Hmmmmmm.... Well, at the moment I would say that there is none. No way to > find induced subgraph of labelled digraphs. Even though for "induced > subgraphs of (simple) labelled undirected graphs" we ca manage a trick. > > See, the problem is that it is rather hard to design a somewhat efficient > data structure for "labelled digraphs". Your problem of "induced subgraph > of labelled simple digraph" (*) could be rather well emulated by a "induced > subgraph of directed multigraph" (though we can't do that either). And a > "proper implementation" should probably deal with non-induced subgraphs as > well, and that's where it becomes hell. To deal with that problem we should > probably copy at low-level, for each label that you have, the graph induced > by all edges having that label. > > The more I think about how this should be implemented, the more it scares > me. > > Nathann > > (*) you don't have paralell edges, right? > -- You received this message because you are subscribed to the Google Groups "sage-support" group. To unsubscribe from this group and stop receiving emails from it, send an email to [email protected]. To post to this group, send email to [email protected]. Visit this group at http://groups.google.com/group/sage-support. For more options, visit https://groups.google.com/d/optout.
