Skip to content
This repository

HTTPS clone URL

Subversion checkout URL

You can clone with HTTPS or Subversion.

Download ZIP

The Python Simple Directed Graph whith Cicle Detector and TopoloGical sorter utilities.

branch: master

Fetching latest commit…

Octocat-spinner-32-eaf2f5

Cannot retrieve the latest commit at this time

Octocat-spinner-32 examples
Octocat-spinner-32 scripts
Octocat-spinner-32 sdag2
Octocat-spinner-32 tests
Octocat-spinner-32 .gitignore
Octocat-spinner-32 MANIFEST.in
Octocat-spinner-32 README.md
Octocat-spinner-32 pipy-dist.sh
Octocat-spinner-32 setup.py
README.md

Py_SDAG2 - Python Simple Directed Acyclic Graph

The Python Simple Directed Graph whith Cicle Detector and TopoloGical sorter utilities.

Authors

Install

sudo pip install py_sdag2

Scripts

tsort.py

Sources from Standard Input:

echo -e 'C A\nA B\nB D\nC D' | tsort.py

Sources from another file:

echo -e 'C A\nA B\nB D\nC D' > verticies.txt
tsort.py verticies.txt

More Options:

tsort.py --help
Usage: tsort.py [options] [FILE [OUT_FILE]]

Options:
  -h, --help            show this help message and exit
  -f FILE, --file=FILE  With no FILE, or when FILE is -, read standard input.
  -o OUT_FILE, --out-file=OUT_FILE
                        Write result to OUT_FILE, default is standard output.
  -s SEP, --separator=SEP
                        Items separator, default is \s regex.
  -q QUIT_SEQ, --quit-sequence=QUIT_SEQ
                        Stop read FILE where line equals QUIT_SEQ, default is
                        :quit.

Tests

import unittest
from sdag2 import DAG, CycleDetectedException

class DAGTest(unittest.TestCase):    
    def test_simple(self):
        '''
        Tests the verticles order in:

        C --> A --> B --> D
        '''

        dag = DAG()
        a = dag.add("A")
        b = dag.add("B")
        c = dag.add("C")
        d = dag.add("D")

        dag.add_edge(c, a)
        dag.add_edge(a, b)
        dag.add_edge(b, d)
        dag.add_edge(c, d)

        rs = dag.topologicaly()

        self.assertTrue(rs.index("C") < rs.index("A"))
        self.assertTrue(rs.index("A") < rs.index("B"))
        self.assertTrue(rs.index("B") < rs.index("D"))
        self.assertTrue(rs.index("C") < rs.index("D"))

    def test_cicle_detect(self):
        '''
        Tests the verticles order in:

        C --> A --> B --> D -> C
        '''

        dag = DAG()
        a = dag.add("A")
        b = dag.add("B")
        c = dag.add("C")
        d = dag.add("D")

        dag.add_edge(c, a)
        dag.add_edge(a, b)
        dag.add_edge(b, d)
        dag.add_edge(c, d)

        try:
            # add cicle at A --> C --> A
            dag.add_edge(a, c)
            raise Exception("Cycle not detected")
        except CycleDetectedException: pass

def main():
    unittest.main()

if __name__ == "__main__":
    main()
Something went wrong with that request. Please try again.