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:

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$
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`

libutilitaspy.data_structures.graphs¶

Previous topic

Next topic

This Page

Navigation

libutilitaspy.data_structures.graphs¶

Previous topic

Next topic

This Page

Quick search

Navigation