Graph.py 1.1 KB

12345678910111213141516171819202122232425262728293031323334353637383940
  1. #!/usr/bin/env python
  2. """
  3. This example shows how to use the class Graph.
  4. The class implements a graph with 'N' vertices. First, you connect the
  5. graph with edges, which have a desired value associated. Then the vertex
  6. values are assigned, which will fail if the graph is cyclic. The vertex
  7. values are assigned such that the two values corresponding to an edge add
  8. up to the desired edge value (mod N).
  9. """
  10. import sys
  11. sys.path.append('..')
  12. from perfect_hash import Graph
  13. G = Graph(3)
  14. assert G.assign_vertex_values() == True
  15. # Now we make an edge between vertex 0 and 1 with desired edge value 2:
  16. G.connect(0, 1, 2)
  17. # Make another edge 1:2 with desired edge value 1:
  18. G.connect(1, 2, 1)
  19. # The graph is still acyclic, and assigning values works:
  20. assert G.assign_vertex_values() == True
  21. assert G.vertex_values == [0, 2, 2]
  22. # What do these values mean?
  23. # When you add the values for edge 0:1 you get 0 + 2 = 2, as desired.
  24. # For edge 1:2 you add 2 + 2 = 4 = 1 (mod 3), as desired.
  25. # Adding edge 0:2 produces a loop, so the graph is no longer acyclic.
  26. # Assigning values fails.
  27. G.connect(0, 2, 0)
  28. assert G.assign_vertex_values() == False
  29. print 'OK'