libutilitaspy.data_structures.graphs

Provides an implementation of directed, labelled graphs.

class libutilitaspy.data_structures.graphs.Node(obj=None)[source]

Nodes of a graph. A node may have an object associated with it, and accessible through its obj atribute.

A node also has a set of incoming edges and a set of outgoing edges.

class libutilitaspy.data_structures.graphs.Edge(source=None, target=None, label=None)[source]

Directed edges between nodes in a graph. An edge has source and target nodes, and possibly a label, which can be any object.

class libutilitaspy.data_structures.graphs.Graph(nodes, edges, source=None, target=None)[source]

This class supports two basic, equivalent, styles of defining graphs:

  1. a graph is given by (N,E,src,trg) where
    • N is a collection of nodes
    • E is a collection of edges
    • src:E \to N is a map associating each edge e in E to its source node src(e) in N
    • trg:E \to N is a map associating each edge e in E to its target node trg(e) in N
  2. a graph is given by (N,E) where
    • N is a collection of nodes

    • E is a collection of edges, where an edge e is a triple (s,t,l) with
      • s is the source node of e,
      • t is the target node of e,
      • l is some label (any object)

In the first style, the connections of an edge are stored in the graph, whereas in the second style, each edge stores a reference to its source and target.

This implementation allows both styles. For example, using style 1) we have:

n1 = Node(1)
n2 = Node(2)
n3 = Node(3)
N = [n1, n2, n3]
e1 = Edge(label='a')
e2 = Edge(label='b')
e3 = Edge(label='a')
E = [e1, e2, e3]
src = Map({e1: n1, e2: n1, e3: n3})
trg = Map({e1: n2, e2: n3, e3: n3})
g = Graph(N, E, src, trg)

On the other hand, using style 2) we have:

n1 = Node(1)
n2 = Node(2)
n3 = Node(3)
N = [n1, n2, n3]
e1 = Edge(n1, n2, label='a')
e2 = Edge(n1, n3, label='b')
e3 = Edge(n3, n3, label='a')
E = [e1, e2, e3]
g = Graph(N, E)

In both cases you can access (where g is a Graph, e is an Edge, and n is a Node):

g.nodes        # this is a set of edges
g.edges        # this is a set of edges
g.source(e)    # this is a Node
g.target(e)    # this is a Node
e.source       # this is a Node 
e.target       # this is a Node 
n.incoming     # this is a set of edges
n.outgoing     # this is a set of edges
Invariants:
For any Graph g:
for every e in g.edges:
e.source == g.source(e) and e.target == g.target(e) and e in e.source.outgoing and e in e.target.incoming
add_node(node)[source]

Adds a node to the graph.

Parameters:node (Node) – A node
add_edge(edge)[source]

Adds an edge to the graph. If the source and/or target nodes of the edge are not already in the graph, they are also added.

Parameters:edge (Edge) – An edge.
class libutilitaspy.data_structures.graphs.GraphHomomorphism(source, target, nodemap, edgemap)[source]

A graph homomorphism h:G_1 \to G_2 between two graphs G_1 = (N_1, E_1, src_1, trg_1) and G_2 = (N_2, E_2, src_2, trg_2) is a pair of maps h = (h_N, h_E) where h_N:N_1 \to N_2 and h_E:E_1 \to E_2 such that for all edges e \in E_1:

  • src_2(h_E(e)) = h_N(src_1(e)), and
  • trg_2(h_E(e)) = h_N(trg_1(e))

Equivalently, a graph homomorphism h:G_1 \to G_2 between two graphs G_1 = (N_1, E_1) and G_2 = (N_2, E_2) is a pair of maps h = (h_N, h_E) where h_N:N_1 \to N_2 and h_E:E_1 \to E_2 such that for all edges e \in E_1:

  • if e = (s,t,l) \in E_1 then h_E(e) = (h_N(s),h_N(t),l) \in E_2.
map(x)[source]
Parameters:x (Node or Edge) – A node or edge in the source graph
Returns:x’s image
Return type:Node if type(x) is Node, Edge if type(x) is Edge

Previous topic

libutilitaspy.data_structures.maps

Next topic

libutilitaspy.data_structures.stacks

This Page