Skip to content

Instantly share code, notes, and snippets.

@timaschew

timaschew/deps.yml

Created March 11, 2021 14:19
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save timaschew/3b08a07243fa6f43773014ef5e705c96 to your computer and use it in GitHub Desktop.
Save timaschew/3b08a07243fa6f43773014ef5e705c96 to your computer and use it in GitHub Desktop.
Download ZIP
Overall distance for a directed graph
Raw
deps.yml
dependencies:
n10:
depends_on:
- n11
n11:
depends_on:
- n12
n12:
depends_on:
- n13
n13:
depends_on:
- n14
n20:
depends_on:
- n21
- n14 # remove for a disconnected graph
n21:
depends_on:
- n22
n22:
depends_on:
- n23
n23:
depends_on: []
# - n20 # cycle
n30:
depends_on:
- n23
- n31
n31:
depends_on:
- n32
# ~~~mermaid
# graph TD
# n10 --> n11
# n11 --> n12
# n12 --> n13
# n13 --> n14
# n20 --> n21
# n20 --> n14
# n21 --> n22
# n22 --> n23
# n30 --> n23
# n30 --> n31
# n31 --> n32
# ~~~
Raw
deps2.yml
dependencies:
base-zero:
depends_on: []
base-one:
depends_on: []
low-a:
depends_on:
- base-one
low-b:
depends_on:
low-c:
depends_on:
- base-zero
- base-one
mid-r:
depends_on: []
mid-p:
depends_on:
- low-b
- low-c
mid-q:
depends_on:
- low-a
high-x:
depends_on:
- mid-p
high-y:
depends_on:
- mid-p
- base-zero
high-z:
depends_on:
- mid-q
- mid-r
- base-one
super:
depends_on:
- high-x
# ~~~mermaid
# graph TD
# low-a --> base-one
# low-c --> base-zero
# low-c --> base-one
# mid-p --> low-b
# mid-p --> low-c
# mid-q --> low-a
# high-x --> mid-p
# high-y --> mid-p
# high-y --> base-zero
# high-z --> mid-q
# high-z --> mid-r
# high-z --> base-one
# super --> high-x
# ~~~
Raw
test.py
#!/usr/bin/env python
# pip install networkx PyYAML markdown md-mermaid
import sys
import yaml
import argparse
import markdown
import networkx as nx
def join_list(list_or_map):
if type(list_or_map) == type({}):
sorted_map = sorted(list_or_map.items())
entries = []
for (distance, values) in sorted_map:
entries.append('{}: {}'.format(distance, ' | '.join(values)))
return '<br>' + '<br>'.join(entries)
return ' | '.join(list_or_map)
class Test:
def __init__(self, args):
self.args = args
with open(self.args.dependency_file) as file:
self.dependency_definitions = yaml.load(file, Loader=yaml.FullLoader)
self.build_graph()
self.calc_distances()
def build_graph(self):
dependencies = self.dependency_definitions['dependencies']
self.graph = nx.DiGraph()
self.undirected_graph = nx.Graph()
mermaid_graph = ['~~~mermaid', 'graph TD']
for (component, value) in dependencies.items():
dependencies = value.get('depends_on')
if dependencies != None:
for d in dependencies:
self.graph.add_edge(component, d)
self.undirected_graph.add_edge(component, d)
mermaid_graph.append("{} --> {}".format(component, d))
mermaid_graph.append('~~~')
self.mermaid = '\n'.join(mermaid_graph)
self.reverse_graph = self.graph.reverse()
def _dump_html_graph(self):
header = """<!DOCTYPE html>
<html>
<head>
<script src="https://cdn.jsdelivr.net/npm/mermaid/dist/mermaid.min.js"></script>
</head>
<body>"""
md_misc = """
# Misc
**root nodes:** {}
**lowest roots:** {}
**leaf nodes:** {}
**highest_leafs:** {}
**distance_nodes_map:** {}
""".format(join_list(self.root_nodes), join_list(self.lowest_roots), join_list(self.leaf_nodes), join_list(self.highest_leafs), join_list(self.distance_nodes_map))
md_content = """
<div style="float: right;">
{}
</div>
# Graph
{}
""".format(markdown.markdown(md_misc), self.mermaid)
body = markdown.markdown(md_content, extensions=['md_mermaid'])
with open(args.html_file, 'w') as file:
file.write(header + body + '</body></html>')
def calc_distances(self):
self.root_nodes = []
self.leaf_nodes = []
for n, adj in self.graph.adjacency():
if len(adj) == 0:
self.root_nodes.append(n)
for n, adj in self.reverse_graph.adjacency():
if len(adj) == 0:
self.leaf_nodes.append(n)
self.max_distance = None
self.lowest_roots = []
self.highest_leafs = []
self.distance_nodes_map = {}
self.node_distance_map = {}
if self.args.html_file:
self._dump_html_graph()
cycles = list(nx.simple_cycles(self.graph))
if len(cycles) > 0:
print('ERROR: Cyclces detected: ', cycles)
sys.exit(1)
connected = nx.is_weakly_connected(self.graph)
if connected == False:
print('ERROR: Graph is not connecteed, inspect the graph via --html for more details')
sys.exit(1)
# TODO: how to build a proper node_distance_map?
# examples of node_distance_map for deps2.yml
# distance_nodes_map: {0: {'base-zero', 'base-one'}, 1: {'low-b', 'low-a', 'low-c'}, 3: {'high-x', 'high-z', 'high-y'}, 2: {'mid-r', 'mid-q', 'mid-p'}, 4: {'super'}}
# to see the graph run: ./test.py --dependency-file deps2.yml
for (node, distance) in self.node_distance_map.items():
if self.distance_nodes_map.get(distance) == None:
self.distance_nodes_map[distance] = set()
self.distance_nodes_map[distance].add(node)
def show_graph(self):
print('mermaid:', self.mermaid)
print('graph as list')
print(nx.to_dict_of_lists(self.graph))
print('root components', self.root_nodes)
print('lowest_roots:', self.lowest_roots)
print('leaf_nodes', self.leaf_nodes)
print('highest_leafs:', self.highest_leafs)
print('distance_nodes_map:', self.distance_nodes_map)
print('node_distance_map:', self.node_distance_map)
print('max_distance:', self.max_distance)
def parse_arguments():
"""
Defines arguments for the script.
:return: arguments parsed from the command-line.
"""
parser = argparse.ArgumentParser()
subparsers = parser.add_subparsers(dest='subparser_name')
# global argument
parser.add_argument('--dependency-file', default='deps.yml', help='File for dependency definitions')
parser.add_argument('--html-file', default='graph.html', help='Create a HTML file with the mermaid graph statistics')
return parser
if __name__ == '__main__':
parser = parse_arguments()
args = parser.parse_args()
test = Test(args)
test.show_graph()
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment