python - How to topological sort a sub/nested graph? -
i've created lightweight graph lib, has 3 objects (vertex, edge, graph) , 1 function (topo_sort), looks like:
class dagerror(exception): pass def topo_sort(graph): sorted_list = [] def visit(vertex): nonlocal sorted_list if vertex.idle: raise dagerror('graph has @ least 1 cycle.') if not vertex.done: vertex.idle = true neighbor in vertex.vertices(): visit(neighbor) vertex.done = true vertex.idle = false sorted_list.insert(0, vertex) queue = [vertex vertex in graph.vertices() if not vertex.done] while queue: visit(queue.pop(0)) return iter(sorted_list) and working fine, if have flat dag. want achieve add subgraphs (or nested graphs) main graph, can see in illustration draw:
nested/sub graph illustration http://f.cl.ly/items/2o0s1c2w1o2c0i0g0l0r/subgraph_illustration3.png
this still dag, if ran function on this, normal topo_sort output going this:
v0, v3, v1, v5, v4, v8, v7, v12, v11, v13, v14, v2, v6, v10, v9, v15, v17, v16 however preferred output when vertices subgraph depends on "processed" before vertices of subgraph processed -- should this:
v0, v1, v8, # vertices of maingraph v3, v5, v4, v12 # vertices of subgraph_0 v7, v11, v13, # vertices of subgraph_1 v14 # vertex of subgraph_0 v2 # vertex of maingraph v6, v10, v9, v15 # vertices of subgraph_2 v16, v17 # vertices of maingraph but not find resources on:
- how "mark" or "store" vertex in graph part of subgraph?
- how sort vertices, based on subgraph dependencies (as example above)?
- how or process subgraph independent graph?
i hope explain problem detailed enough -- although if missing, please let me know, , extend question missing parts.
thanks in advance!
edit:
i found (boost graph library, bgl) , looks solves similar (or same?) problem have, although, i'm not familiar c++, don't understand how working , doing -- put here, maybe find helpful answer questions..
edit 2:
i accept pseudocode, not python! of course if existed python library knows this, i'm interested in it, however, don't want use such huge library graph-tools example -- that's why created own, prefer implementations more libs.
might bit late you, other people similar problems:
how "mark" or "store" vertex in graph part of subgraph?
why not give vertex object attribute subgraph holding integer or string labeling subgraph vertex belongs? (if want use networkx, use node attribute dictionary) way, can check subgraph attribute in sorting algorithm.
how sort vertices, based on subgraph dependencies (as >example above)?
i'm not expert on topological sorting, asuming every vertex "knows" subgraph belongs to, came (using networkx, can implement pieces used in own library): code below gathers "dependencies" described (all vertices need come before current one). can use information modify topol_sort() function in such way, appends current vertex list if not vertices in dependencies on list.
import networkx nx # define graph , subgraphs suitable networkx g = ... subgraphs = ... subgraph in subgraphs: # find vertices current subgraph depends on dependencies = set() vertex in subgraph: anc = nx.ancestors(g, vertex) # anc set of vertices having path 'vertex' dependencies.union(anc) dependencies -= subgraph.nodes() # store these dependencies under every vertex of current subgraph vertex in subgraph: g[vertex].node['depends'] = dependencies # run modified topological sorting topo_sort_mod(g) how or process subgraph independent graph?
i'm not sure want here. maybe this helps (again, using networkx), part:
to create subgraph own copy of edge/node attributes use: nx.graph(g.subgraph(nbunch))
if edge attributes containers, deep copy can obtained using: g.subgraph(nbunch).copy()
i hope helps ... :)
