How to topological sort a sub/nested graph?

Question

I've created a lightweight graph lib, which has 3 objects (Vertex, Edge, Graph) and 1 function (topo_sort), which 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 at least one cycle.')
        if not vertex.done:
            vertex.idle = True
            for neighbor in vertex.vertices():
                visit(neighbor)
            vertex.done = True
            vertex.idle = False
            sorted_list.insert(0, vertex)
    queue = [vertex for vertex in graph.vertices() if not vertex.done]
    while queue:
        visit(queue.pop(0))
    return iter(sorted_list)

And this is working fine, if I have a flat DAG. But what I want to achieve is to add subgraphs (or nested graphs) into my main graph, as you can see in this illustration I draw:

This is still a DAG, so if I ran my function on this, the normal topo_sort output is going to be something like this:

V0, V3, V1, V5, V4, V8, V7, V12, V11, V13, V14, V2, V6, V10, V9, V15, V17, V16

However my preferred output would be when all the vertices a subgraph depends on are "processed" before the vertices of the subgraph is processed -- so it should be something like 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 I could not find any resources on:

• how to "mark" or "store" a vertex in a graph as part of a subgraph?
• how to sort the vertices, based on their subgraph dependencies (as the example above)?
• how to get or process the subgraph as an independent graph?

I hope I could explain my problem detailed enough -- although if something is missing, please let me know, and I will extend my question with the missing parts.

Thanks in advance!

---

EDIT:

I found this (Boost Graph Library, BGL) and it looks like it solves a very similar (or exactly the same?) problem that I have, although, I'm not familiar with C++, so I don't understand how it is working and what exactly it is doing -- but I put this here, maybe someone will find it helpful to answer my questions..

---

EDIT 2:

I also accept pseudocode, not just python! Of course if an existed python library knows this, I'm interested in it, however, I don't want to use such a huge library as graph-tools for example -- that's why I created my own, so I prefer implementations more than libs.

Lactoscope

Answer 1

Might be a bit late for you, but for other people with similar problems:

how to "mark" or "store" a vertex in a graph as part of a subgraph?

Why not just give the vertex object an attribute subgraph holding an integer or a string labeling to which subgraph the vertex belongs? (If you want to use NetworkX, use the node attribute dictionary) This way, you can check this subgraph attribute in your sorting algorithm.

how to sort the vertices, based on their subgraph dependencies (as the >example above)?

I'm not an expert on topological sorting, but asuming every vertex "knows" the subgraph it belongs to, this is what I came up with (using NetworkX, but you can easily implement the pieces I used in your own library): The code below gathers all the "dependencies" you described (all the vertices that need to come before the current one). You can use this information to modify your topol_sort() function in such a way, that it only appends the current vertex to the list if not all the vertices in its dependencies are already on the list.

import networkx as nx

# define the graph and the subgraphs suitable for NetworkX
G = ...
subgraphs = ...

for subgraph in subgraphs:
    # find all vertices that the current subgraph depends on
    dependencies = set()
    for vertex in subgraph:
        anc = nx.ancestors(G, vertex) # anc is the set of all vertices having a path to 'vertex'
        dependencies.union(anc)
    dependencies -= subgraph.nodes()
    # store these dependencies under every vertex of the current subgraph
    for vertex in subgraph:
        G[vertex].node['depends'] = dependencies

# run modified topological sorting
topo_sort_mod(G)

how to get or process the subgraph as an independent graph?

I'm not sure what you exactly want here. Maybe this helps (again, using NetworkX), especially this part:

To create a subgraph with its own copy of the edge/node attributes use: nx.Graph(G.subgraph(nbunch))

If edge attributes are containers, a deep copy can be obtained using: G.subgraph(nbunch).copy()

I hope this helps anyone ... :)

Fringe

Answer 2

read your statement about Graph-tools but still not sure if you like to use a library to do a certain job or you like to understand how to write it yourself.

Maybe you look at

General Samples
[http://networkx.github.io/examples.html][1]

DAG Example
[http://networkx.lanl.gov/archive/networkx-1.6/_modules/networkx/algorithms/dag.html][2]

and see if it helps you to solve your problem?

Lm

Thanks @Peter -- I already knew networkx, but I did a recheck on it, and eventhough I read all the articles mentioning the word 'subgraph' it seems, that networkx doesn't have the features I'm looking for (or at least, not that I'm aware of) -- although it has a subgraph() method, but it only re-referencing a part of the graph, which doesn't effect the sorting algorithm. Anyway, thanks again, but none of these links were helpful..(BTW I prefer to understand and implement this on my own) – Lactoscope