A collection of algorithms for solving Maximum Ink Partial Edge Drawing Problems
Project description
partialedge
This library contains algorithms for solving Maximum Ink Partial Edge Drawing problems, MaxPED, MaxSPED and MaxSHPED in particular. The implementation is based on the algorithms presented in the publication from Hummel et al[1] while using the htd[2] library from Michael Abseher for tree decomposition.
The CrossingResolution algorithm solves MaxSHPED, while the Tree algorithm can solve MaxSPED where the intersection graph forms a tree. The TreeDecomposition algorithm is applicable to either MaxPED or MaxSPED with no restriction on the intersection graph. However, depending on the treewidth of the tree decomposition, the execution may require too much runtime or memory space.
Source | PED | SPED | SHPED |
---|---|---|---|
Installation
Use the package manager pip to install partialedge.
pip install partialedge
Usage
Command Line
python -m partialedge
positional arguments:
input path to input file or directory depending on mode
optional arguments:
-h, --help show this help message and exit
--mode {single,set,dir}
process a single input file, a file containing a set
of graph drawings, or a directory of set files
--symmetric input will be processed as symmetric PED problem
--homogeneous input will be processed as homogeneous PED problem
--json JSON_DIR, -j JSON_DIR
store result data at the given directory
--image IMAGE_DIR, -i IMAGE_DIR
store result image at the given directory
--include-source, -s store source graph image with the result image
--verbose, -v v count determines logging verbosity level
Development
import logging
from partialedge.graph import graph_window as gw
from partialedge.algorithm import ped_algorithm as alg
logger = logging.getLogger("ped")
logger.setLevel(logging.INFO - 3)
# all high-level features are exposed via an algorithm object
# the positional parameter determines output filenames
# algorithm classes: TreeDecompositionAlgorithm, TreeAlgorithm, CrossingResolutionAlgorithm
algorithm = alg.TreeDecompositionAlgorithm("sample", symmetric=False, logger=logger)
# either create a random graph layout or load an existing one
algorithm.create_graph(15, 20, layout="spring")
# algorithm.load_graph_from_graph_file(file_path="resources/sample/json/source/sample.json")
# start execution
algorithm.perform_algorithm()
# export source and output
algorithm.export_source_graph(dir_path="resources/sample/json/source")
algorithm.export_json_result(dir_path="resources/sample/json/result")
algorithm.export_image_source(dir_path="resources/sample/image/source")
algorithm.export_image_result(dir_path="resources/sample/image/result")
# create plot of source graph
algorithm.set_edges_full()
source = gw.GraphWindow()
source.draw_graph(algorithm.graph)
# create plot of result graph
algorithm.set_edges_partial()
result = gw.GraphWindow()
result.draw_graph(algorithm.graph)
# show matplotlib plots
source.show()
# close matplotlib resources
source.close()
result.close()
File Format
Input
The input file for a single graph must be in the same format as the example below. In set mode the json file has to contain a list of named single graphs. The directory mode requires the path to a directory with set files as input.
{
"edges": [
{
"incident_nodes": [
0,
1
]
}
],
"nodes": [
{
"coordinates": [
0.2215272649584424,
-1.0
],
"index": 0
},
{
"coordinates": [
-0.2215272649584424,
1.0
],
"index": 1
}
]
}
Output
The json result file contains a lot of information that can be used for statistical analysis. In the graph field, the number of nodes and edges as well as the ink value is stored, in addition to the full drawing of the source graph. As it has a large impact on runtime and memory consumption, the intersection graph with details about its size and the number of crossings per node is stored in the intersection field. The result field contains all stub values of the maximum ink partial edge drawing in relation to edges of the input graph drawing. It also stores meta data consisting of the resulting ink value, treewidth of the tree decomposition on the intersection graph, and a boolean about whether the problem had the symmetric constraint. The success field on the highest level is true, if execution of the algorithm completed uninterrupted, and the time field contains the runtime in seconds.
{
"graph": {
"edge_data": {
"edge_count": 1,
"edges": [
{
"incident_nodes": [
0,
1
]
}
]
},
"ink": 2.048486591725675,
"node_data": {
"node_count": 2,
"nodes": [
{
"coordinates": [
0.2215272649584424,
-1.0
],
"index": 0
},
{
"coordinates": [
-0.2215272649584424,
1.0
],
"index": 1
}
]
}
},
"intersection": {
"delta_count": {
"0": 1
},
"edge_count": 0,
"edges": [],
"node_count": 1,
"nodes": [
{
"delta": 0,
"index": 0
}
]
},
"result": {
"edges": [
{
"incident_nodes": [
0,
1
],
"stub": [
0.5,
0.5
]
}
],
"ink": 2.048486591725675,
"symmetric": false,
"tree_width": 0
},
"success": true,
"time": {
"algorithm": 0.00013890000000049696,
"init_datastructure": 9.380000000014377e-05,
"tree_decomposition": 0.12066659999999985
}
}
Contributing
No major updates are planned at the moment. Anyone willing to contribute is welcome to create bug reports and pull requests at the project page
License
Citations
Project details
Release history Release notifications | RSS feed
Download files
Download the file for your platform. If you're not sure which to choose, learn more about installing packages.
Source Distribution
Built Distribution
Hashes for partialedge-1.0.1-py3-none-any.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 9f5e0e450fca862265e031ca6d26c9cf157a1cb47c69670960e2d20f1b18530f |
|
MD5 | 1312853ad53b01b5e92564784ddcae73 |
|
BLAKE2b-256 | abb93828b55d8387067f21b2a2cc55a5cd9e61f5ff04c60740431fd743954549 |