copy, cut and paste of subgraphs

classic Classic list List threaded Threaded
4 messages Options
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

copy, cut and paste of subgraphs

bsdz
Hi

Graph Tool looks like a great comprehensive library. I am very new to it and sorry, in advance, if this question or something similar has been answered before. I had a good search and couldn't find a solution.

I am creating directed graphs and would like to search those graphs for subgraphs that have corresponding labels on their vertices and edges. I then would like to cut those subgraphs out, potentially make additional copies, then paste those subgraphs attached by edges to different vertices of the remain graph.

So for example in the following code:

def label_edges(g):
    eprop = g.new_edge_property("string") 
    for e in g.edges():
        eprop[e] = ">" if e.source() > e.target() else "<"
    g.edge_properties["name"] = eprop 

g1 = Graph(directed=True)
g1.add_edge_list([[0,1],[1,2],[2,3],[3,4],[4,0]])
g1.add_edge_list([[5,6],[6,7],[7,5]])
g1.add_edge_list([[8,9],[9,10],[10,8]])
g1.add_edge_list([[11,12],[12,13],[13,14],[14,11]])
g1.add_edge_list([[11,0],[12,5],[13,8]])
label_edges(g1)

h = Graph(directed=True)
h.add_edge_list([[0,1],[1,2],[2,3],[3,4],[4,0]])
label_edges(h)

I would like to take subgraphs of g1 that match h including edge labels. I know i can find these subgraphs using:

subgraph_isomorphism(h, g1, edge_label=(h.edge_properties["name"],g1.edge_properties["name"]))

I then might like to paste that subgraph in a way to create a new graph g2 that might look like:

g2 = Graph(directed=True)
g2.add_edge_list([[0,1],[1,2],[2,3],[3,4],[4,0]])
g2.add_edge_list([[5,6],[6,7],[7,5]])
g2.add_edge_list([[8,9],[9,10],[10,8]])
g2.add_edge_list([[11,12],[12,13],[13,14],[14,11]])
g2.add_edge_list([[12,5],[13,8]])
g2.add_edge_list([[15,16],[16,17],[17,18],[18,19],[19,15]])
g2.add_edge_list([[9,0],[10,15]])
label_edges(g2)

Please ignore the the fact I have used multiple calls to add_edge_list() to generate these example graphs. This is just an artifact of creating the above example. In my real use case I will just be presented with a random vertex/edge labelled graph.

Is there any recommended way to do this?

Thanks
Blair
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: copy, cut and paste of subgraphs

Tiago Peixoto
Administrator
On 04.07.2017 20:50, bsdz wrote:
> Is there any recommended way to do this?

There is no special function to achieve this; you have to implement it using
the basic API. But it is simple: just extract the list of edges in the
subgraph, construct a vertex-to-vertex mapping that amounts to your
"pasting", translate the edge endpoints accordingly, and add the translated
edges to your graph.

--
Tiago de Paula Peixoto <[hidden email]>
_______________________________________________
graph-tool mailing list
[hidden email]
https://lists.skewed.de/mailman/listinfo/graph-tool
--
Tiago de Paula Peixoto <tiago@skewed.de>
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: copy, cut and paste of subgraphs

bsdz
Thanks for your suggestion. I guess I had already considered that but think I might be missing something obvious. How do I get links to the actual vertices from the property map that subgraph_isomorphism() returns?

For example, I tried this:

<code>
sgs = subgraph_isomorphism(h, g1, ...)
for vi in sgs[0]:
    g1.remove_vertex(g1.vertex(vi))
</code>

but this deletes vertices in g1 based on index and this index appears to alter after deleting the 1st subgraph so might not behave correctly on deleting a 2nd subgraph.

Also how would I create a vertex-to-vertex mapping of the subgraph (sgs[0]) while retaining the edges? What type of mapping is this? Perhaps there's an example or specific function that might help? I have read most of relevant documentation but it's still not very clear to me :(
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: copy, cut and paste of subgraphs

bsdz
Actually I think I know what you might be suggesting. In my example use the actual subgraph "h" and copy that where I need it. Just deleting the vertices that the property map provides from the subgraph_isomorphism() function. I'll give that go, thanks.
Loading...