Graph

A basic graph class, and base for all Graph mixins.

In graph theoretic terms, this represents a bridge multigraph.
This means that it supports both directed and undirected edges,
loops, and parallel edges.

Note that element names must be unique within this graph; non
unique element names between graphs are not only allowable, but
encouraged if you wish for those elements to compare equally
between graphs.

Because of its generality, it is suitable as a general-purpose
Graph representation.

Data

Node

Type of the nodes to be used in this Graph

Node = Node

Edge

Type of the edges to be used in this Graph

Edge = Edge

_nodes

Backing data store for Node objects. Currently a dictionary of name –> object mappings in the base implementation.

_edges

Backing data store for Edge objects. Currently a dictionary of name –> object mappings in the base implementation.

Properties

def nodes(self):

Returns an iterator over all the nodes in the graph.

def edges(self):

Returns an iterator over all the edges in the graph.

def size(self):

Reports the number of edges in the graph.

Usage:

>>> g = Graph()
>>> n1, n2 = g.add_node(), g.add_node()  
>>> g.size  
0  
>>> e = g.add_edge(n1, n2)  
>>> g.size  
1

def order(self):

Reports the number of nodes in the graph.

Usage:

>>> g = Graph()
>>> g.order  
0  
>>> n = g.add_node()  
>>> g.order  
1

Constructors

def __init__(self):

Base initializer for Graphs.

Usage:

  >>> g = Graph()

Operators

def __contains__(self, element):

Returns True if the element is a member of the graph.

Usage:

        >>> g = Graph()
        >>> n = g.add_node()  
        >>> n in g  
        True

def __getitem__(self, name):

Returns the element corresponding to the given name or the given element’s name.

Raises KeyError if it is not found.

def __and__(self, other):

Maps the & operator to the intersection operation.

def __or__(self, other):

Maps the | operator to the union operation.

def __sub__(self, other):

Maps the – operator to the difference operation.

def __eq__(self, other):

Compares based on node and edge names.

def __lt__(self, other):

Compares based on containment.

This returns True if this graph is contained in other.

def __gt__(self, other):

Compares baed on containment.

This returns True if it contains other, False otherwise.

Convenience Functions

def get_element(self, item):

Takes an element or a name and returns an element.

If no element corresponds to the given name, raises KeyError.

def get_name(self, item):

Takes an element or a name and returns a name.

If no element corresponds to the given name, raises KeyError

Graph Construction Tools

def add_node(self, name=None, **kwargs):

Adds a node with no edges to the current graph.

The name argument, if given, should be hashable and unique in this graph.

Usage:

>>> g = Graph()
>>> g.add_node("bob", weight=5)  
Node(name=bob, weight=5)

def add_edge(self, start, end, name=None, is_directed=True, **kwargs):

Adds an edge to the current graph.

The start and end arguments can be either nodes or node names.

The name argument, if given, should be hashable and unique in this graph.

The optional argument “is_directed” specifies whether the given edge should
be directed or undirected.

Usage: 

>>> g = Graph()
>>> n1, n2 = g.add_node(), g.add_node()  
>>> g.add_edge(n1, n2, weight=5)  
Edge(weight=5)

def remove_node(self, node):

Removes a node from the graph.

Usage:

>>> g = Graph()
>>> n = g.add_node()  
>>> g.remove_node(n)  
>>> n in g  
False

def remove_edge(self, edge):

Removes an edge from the graph.

Usage:

>>> g = Graph()
>>> n1, n2 = g.add_node(), g.add_node()  
>>> e = g.add_edge(n1, n2)  
>>> g.remove_edge(e)  
>>> e in g  
False

Graph Inspection Tools

def search_nodes(self, **kwargs):

Convenience function to get nodes based on some properties.

Usage:

>>> g = Graph()
>>> n1 = g.add_node("bob")  
>>> n2 = g.add_node("bill")  
>>> for node in g.search_nodes(name="bob"):  
...     print(node)  
Node(name="bob")

def search_edges(self, **kwargs):

Convenience function to get edges based on some properties.

Usage:

>>> g = Graph()
>>> n1, n2 = g.add_node(), g.add_node()  
>>> e1 = g.add_edge(n1, n2, weight=4)  
>>> e2 = g.add_edge(n1, n2, "n1->n2", weight=5)  
>>> for edge in g.search_edges(weight=5):  
...     print(edge)  
Edge(name=n1->n2, weight=5)

def get_common_edges(self, n1, n2):

Gets the common edges between the two nodes.

Usage:

>>> g = Graph()
>>> n1 = g.add_node()  
>>> n2 = g.add_node()  
>>> e = g.add_edge(n1, n2, "fluffy")  
>>> g.get_common_edges(n1, n2)  
{Edge(name="Fluffy")}

def walk_nodes(self, start, reverse=False):

Provides a generator for application-defined walks.

The start argument can be either a name or a label.

The optional reverse argument can be used to do a reverse
walk, ie, only walking down incoming edges.

Usage:

>>> g = Graph()
>>> n1 = g.add_node()  
>>> n2 = g.add_node()  
>>> e1 = g.add_edge(n1, n2)  
>>> w = g.walk_nodes()  
>>> for adjacent_nodes in w:  
...         next_node = adjacent_nodes.pop()  
...     w.send(next_node)

def walk_edges(self, start):

Provides a generator for application-defined walks.

Usage is identical to walk_nodes, excepting only that it accepts,
and yields, Edges in the place of Nodes.

def heuristic_walk(self, start, selector, reverse=False):

Traverses the graph using selector as a selection filter on the adjacent nodes.

The optional reverse argument allows you to do a reverse walk, ie, only finding
adjacencies according to incoming edges rather than outgoing edges.

Usage:

>>> g = Graph()
>>> g.add_node("A")  
>>> g.add_node("B")  
>>> g.add_edge("A", "B", "AB")  
>>> def selector(adjacent_nodes):  
... return adjacent_nodes.pop()  
...  
>>> for node in g.heuristic_walk("A", selector):  
...     print(node.name)  
B

def heuristic_traversal(self, root, selector):

Traverses the graph using selector as a selection filter on the unvisited nodes.

Usage:

>>> g = Graph()
>>> n1, n2 = g.add_node("A"), g.add_node("B")  
>>> e = g.add_edge(n1, n2)  
>>> for node in g.a_star_traversal(n1, lambda s: s.pop()):  
>>>     print(node)  
Node(name="A")  
Node(name="B")

def depth_first_traversal(self, root):

Traverses the graph by visiting a node, then a child of that node, and so on.

Usage:

>>> g = Graph()
>>> a, b = g.add_node("A"), g.add_node("B")  
>>> c, d = g.add_node("C"), g.add_node("D")  
>>> e1, e2 = g.add_edge(a, b), g.add_edge(a, c)  
>>> e3, e4 = g.add_edge(b, d), g.add_edge(c, d)  
>>> for node in g.depth_first_traversal(a):  
>>>     print(node)  
Node(name="A")  
Node(name="B")  
Node(name="D")  
Node(name="C")

def breadth_first_traversal(self, root):

Traverses the graph by visiting a node, then each of its children, then their children.

Usage:

>>> g = Graph()
>>> a, b = g.add_node("A"), g.add_node("B")  
>>> c, d = g.add_node("C"), g.add_node("D")  
>>> e1, e2 = g.add_edge(a, b), g.add_edge(a, c)  
>>> e3, e4 = g.add_edge(b, d), g.add_edge(c, d)  
>>> for node in g.breadth_first_traversal(a):  
>>>     print(node)  
Node(name="A")  
Node(name="B")  
Node(name="C")  
Node(name="D")

def get_connected_components(self):

Gets all the connected components from the graph.

Returns a list of sets of vertices.

Usage:

>>> g = Graph()
    >>> n1 = g.add_node(group=1)  
>>> n2 = g.add_node(group=1)  
>>> n3 = g.add_node(group=2)  
>>> e1 = g.add_edge(n1, n2)  
>>> g.get_connected_components()  
    [{Node(group=1), Node(group=1)}, {Node(group=2)}]

def get_strongly_connected(self):

Returns a list of all strongly connected components.

Each SCC is expressed as a set of vertices.

Usage is identical to get_connected_components.

def get_shortest_paths(self, source, get_weight=lambda e: 1):

Finds the shortest path to all connected nodes from source.

The optional get_weight argument should be a callable that
accepts an edge and returns its weight.

Returns a dictionary of node –> (path_length, [edges_traversed])
mappings.

Usage:

>>> g = Graph()
>>> n1 = g.add_node("A")  
>>> n2 = g.add_node("B")  
>>> n3 = g.add_node("C")  
    >>> n4 = g.add_node("D")  
>>> e1 = g.add_edge(n1, n2, weight=10)  
>>> e2 = g.add_edge(n1, n4, weight=1)  
>>> e3 = g.add_edge(n2, n3, weight=1)  
>>> e4 = g.add_edge(n3, n4, weight=1)  
>>> d = g.get_shortest_paths(n1, get_weight=lambda e: e.weight)  
>>> d[n1]  
(0, [])  
>>> d[n2]  
(10, [Edge(weight=10)])  
>>> d[n3]  
(11, [Edge(weight=10), Edge(weight=1)])  
>>> d[n4]  
(1, [Edge(weight=1)])

Graph Rewriting Tools

def move_edge(self, edge, start=None, end=None):

Moves the edge, leaving its data intact.

Does not change a directed edge into an undirected edge.

def contract_edge(self, edge, node_data):

Contracts the given edge, merging its endpoints.

node_data should be a callable that returns a dictionary.
That dictionary will be used to initialize the new node.

It returns the node so created.

There are two caveats about using this:

  • The name passed back by node_data, if present, must
    still be unique- and the old nodes can’t be deleted
    until after the new one is added.

  • Note that if multiple edges exist between the two nodes,
    this will still contract them!

def transpose(self):

Reverses the directions on all edges in the current graph.

def induce_subgraph(self, *nodes):

Returns a new graph composed of only the specified nodes and their mutual edges.

Usage:

Set up your graph:

    >>> enterprise = Graph()
    >>> kirk = enterprise.add_node("kirk")  
    >>> spock = enterprise.add_node("spock")  
    >>> bones = enterprise.add_node("mccoy")  
    >>> enterprise.add_edge(kirk, spock)  
    >>> enterprise.add_edge(kirk, bones)

As you can see, it has 3 nodes and two edges:

    >>> enterprise.order
    3  
    >>> enterprise.size  
    2

    Now we induce a subgraph that includes spock and bones but
not the captain:  

    >>> new_mission = enterprise.induce_subgraph(spock, bones)

And can see that it has two nodes- spock and bones- but no edges:

    >>> new_mission.order
    2  
    >>> new_mission.size  
    0

def edge_induce_subgraph(self, *edges):

Similar to induce_subgraph but accepting edges rather than nodes.

Graph Comparison Tools

def union(self, other):

Returns a new graph with all nodes and edges in either of its parents.

Usage:

>>> g1 = Graph()
>>> g2 = Graph()  
>>> a = g1.add_node(1)  
>>> b = g1.add_node(3)  
>>> c = g1.add_node(5)  
>>> ab = g1.add_edge(a, b, 2)  
>>> bc = g1.add_edge(b, c, 4)  
>>> d = g2.add_node(3)  
>>> e = g2.add_node(5)  
>>> f = g2.add_node(7)  
>>> de = g2.add_edge(d, e, 4)  
>>> ef = g2.add_edge(e, f, 6)  
>>> g3 = g1 | g2  
>>> [node.name for node in g3.nodes]  
[1, 3, 5, 7]  
>>> [edge.name for edge in g3.edges]  
[2, 4, 6]

def intersection(self, other):

Returns a graph containing only the nodes and edges in both of its parents.

Note that both endpoints must exist in the new graph for an edge to exist.

Usage:

>>> g1 = Graph()
>>> g2 = Graph()  
>>> a = g1.add_node(1)  
>>> b = g1.add_node(3)  
>>> c = g1.add_node(5)  
>>> ab = g1.add_edge(a, b, 2)  
>>> bc = g1.add_edge(b, c, 4)  
>>> d = g2.add_node(3)  
>>> e = g2.add_node(5)  
>>> f = g2.add_node(7)  
>>> de = g2.add_edge(d, e, 4)  
>>> ef = g2.add_edge(e, f, 6)  
>>> g3 = g1 & g2  
>>> [node.name for node in g3.nodes]  
[3, 5]  
>>> [edge.name for edge in g3.edges]  
[4]

def difference(self, other):

Return a graph composed of the nodes and edges not in the other.

Usage:

>>> g1 = Graph()
>>> g2 = Graph()  
>>> a = g1.add_node(1)  
>>> b = g1.add_node(3)  
>>> c = g1.add_node(5)  
>>> ab = g1.add_edge(a, b, 2)  
>>> bc = g1.add_edge(b, c, 4)  
>>> d = g2.add_node(3)  
>>> e = g2.add_node(5)  
>>> f = g2.add_node(7)  
>>> de = g2.add_edge(d, e, 4)  
>>> ef = g2.add_edge(e, f, 6)  
>>> g3 = g1 & g2  
>>> [node.name for node in g3.nodes]  
[1]  
>>> [edge.name for edge in g3.edges]  
[]

def contains(self, other):

Tests to see if other is a subgraph of this graph.

Comparison is based on names, and compares both nodes and edges.