Harald Ujc - Screenpop Software Inc.
A python library for planarity testing and rendering of ladder type graphs. Built with Visual Studio Code and Python 3.7.0 32-bit, 3.7.4 64-bit Conda on Windows 10 and Python 3.7.3 64-bit, 3.7.3 64-bit Conda on Mac OS X.
The algorithm is sourced from 'Efficient Planarity Testing' by John Hopcroft and Robert Tarjan
pyladder is an exercise in translating an ANSI 'C' program to a python class. The program will take a list of nodes representing a connected graph in the plane. It will then attempt to generate a visual display of the graph, and advise if the graph is planar or not.
Note that as this is a learning exercise, some of the style used will not adhere to generally accepted python patterns.
There is an upper limit on the number of connections and nodes. This is not a limitation of the algorithm, rather due to the original 'C' program being a proof-of-concept and there was no appetite for dynamic memory management and fixed arrays were used instead.
The pyladder package can be used to display a ladder representing protective interlock logic.
The pyladder package can be used to render a maze or connected points in space in real time from a list of coordinates. This is much more portable, space saving and dynamic as opposed to a fixed graphical representation in files or memory.
The input node list could represent a list of electronic parts and the output could then be used to create an circuit board etch where the requirement is that the connecting edges cannot cross, for obvious reasons.
Note: The pyladder package is available at the Python Package Index. All examples below require installation of the pyladder package via:
A python dictionary describing the ladder as follows: The key-value pair is key = a string label identifying the node value = a list of nodes to which this node connects. The first element of each list is the node key, and the subsequent items are the keys of the nodes to which this node connects Example :
The above code will return true or false according to the ladder planarity and will display as per below (see pyladder_client_dict_example.py for a full implementation example):
LINK17.DAT file, when transformed into the dictionary format, will display as per below (the *.DAT files are discussed below, see pyladder_file_example.py):
LINK18.DAT is an example of a non-planar ladder. A call to display_graph_plot will return False, and no visual plot will be displayed.
Two lists containing the ladder nodes as follows: The first list represents a node and its connections to other nodes i.e. [x, y, z, ...] where x is the subject node and y, z, ... are the nodes to which it connects
The second list is metadata about the first list, and is used only by matplotlib ['node description 1', 'node description 2', 'node description 3',...] where 'node description 1 mapes to 'x' in the first list
Refer to pyladder_client_example.py for full implementation details
The call to gen_graph will return true or false according to the ladder planarity.
Here, coors is a list of coordinate pair lists representing the line segments (edges) to be plotted. This list in conjunction with graph_node_labels can be used with matplotlib to display the graph:
[ [[x1,y1], [x2,y2]], [[x3,y3], [x4,y4]], ..., [[xN,yN], [xM,yM]], ]
A list containing coordinate pair lists where each list pair represents an edge connecting two nodes.
The call to display_graph_plot_edges will return true or false according to the ladder planarity, and display as follow (see pyladder_edge_list_example.py):
The *DAT files were the input files to the original 'C' command line program. Format used is one node identifier per line. The first node is the 'source', and every node after and up to '0' are the nodes to which the source connects.
10 20 25 40 0 20 39 0 ...
The sample client file pyladder_client_file.py can be used to injest and parse the *.DAT files into the dictionary data structure format required by pyladder.py, as described in calling convention 1 and the ladder_input dictionary specifically.
The following files are examples of non-planar ladders: LINK2.DAT LINK4.DAT LINK10.DAT LINK18.DAT
1; The label for the top 'rung' is not displayed in the matplotlib line plot. Status = Fixed 2; The ladder representation in file LINK32.DAT is returning a 'graph rendering failed' message. Status = Fixed 3; Improve the visual rendering by including a marker on the vertical line segments for each level of the ladder. This would be helpful when using the class to render PLC ladder logic. Status = Oustanding 4; Comment out debug lines. Presently the command line output is very verbose. Status = Fixed 5; File LINK36.DAT is not rendering correctly (out of order along y-axis). Status = Fixed 6; File LINK20.DAT is not rendering correctly (out of order along y-axis). Status = Fixed 7; File LINK30.DAT is not rendering correctly. Status = Fixed, however the ladder is too large to display, must find a scrollable plotting tool. 8; Implement a scrollable visual plotting library. Status = Outstanding 9; Implement a non-visual method call that returns only a planar/non-planar boolean. Can be used for batch jobs. 10; Transition this issue log to github issues. 11; Plot titles not appearing. Status = Fixed. 12; Add boolean to planarity check to enable or disable visual display of ladder. Status = Complete. 13; Visual display of non-planar ladders is no longer generated. Only False is returned. Status = Complete.