Skip to content

uknfire/tsmpy

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

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
case1 case2
bend case grid case
bend grid

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
  • Fix overlay
  • Support node degree > 4
  • Support cut-edges