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:
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.
There can be more than one topological sorting for a graph. Another topological sorting of the following graph is “4 5 2 3 1 0”. The first vertex in topological sorting is always a vertex with an in-degree of 0 (a vertex with no incoming edges).
We also can't topologically sort an undirected graph since each edge in an undirected graph creates a cycle. So topological sorts only apply to directed, acyclic (no cycles) graphs - or DAGs.
Number of different topological orderings possible = 6. Thus, Correct answer is 6.
Precisely, a topological sort is a graph traversal in which each node v is visited only after all its dependencies are visited. A topological ordering is possible if and only if the graph has no directed cycles, that is, if it is a directed acyclic graph (DAG).
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 ... :)
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With