Introduction

An implementation of orthogonal drawing algorithm in Python

Main idea comes from A Generic Framework for the Topology-Shape-Metrics Based Layout

How to run code

Install requirements

pip install -r requirements.txt

Usage

# in root dir
import networkx as nx
from tsmpy import TSM
from matplotlib import pyplot as plt

G = nx.Graph(nx.read_gml("test/inputs/case2.gml"))

# initial layout, it will be converted to an embedding
pos = {node: eval(node) for node in G}

# pos is an optional, if pos is None, embedding will be given by nx.check_planarity

# use linear programming to solve minimum cost flow program
tsm = TSM(G, pos)

# or use nx.min_cost_flow to solve minimum cost flow program
# it is faster but produces worse result
# tsm = TSM(G, pos, uselp=False)

tsm.display()
plt.savefig("test/outputs/case2.lp.svg")
plt.close()

Run test

# show help
python test.py -h

# run all tests
python test.py

# run all tests in TestGML
python test.py TestGML

Example

case1	case2

bend case	grid case

Playground

Try editing original case2 graph with yed

Requirements for input graph

• Planar
• Connected
• Max node degree is no more than 4
• No selfloop

Features

• Using linear programing to solve minimum-cost flow problem, to reduce number of bends

TODO

• [ ] Cleaner code
• [ ] More comments
• [x] Fix overlay
• [ ] Support node degree > 4
• [x] Support cut-edges