graphi.abc module¶
-
class
graphi.abc.
AdjacencyList
¶ Bases:
dict
,_abcoll.MutableMapping
Edge values of nodes to a node in a graph
This represents edges in a
graph
originating fromnode
as a mapping to their values. For example, the edgegraph[a:b] = c
corresponds toadjacency[b] = c
for nodea
.
-
exception
graphi.abc.
AdjacencyListTypeError
(item)¶ Bases:
exceptions.TypeError
AdjacencyList set with an incorrect type
-
exception
graphi.abc.
EdgeError
¶ Bases:
exceptions.Exception
Graph edge not found
-
class
graphi.abc.
EdgeView
(graph)¶ Bases:
graphi.abc.GraphView
View on the edges in a graph
-
class
graphi.abc.
Graph
(*source, **kwargs)¶ Bases:
_abcoll.Container
Abstract Base Class for graphs representing values of edges between nodes
A
Graph
is a container for primitive nodes and edges. There are three types of elements handled by a graph:- primitive nodes,
- slice-like edges as pairs of nodes, and
- primitive edge values.
Both nodes and edge values are conceptually similar to keys and values of
dict
. However, the concept of node pairs as edges adds additional functionality. The fixed relation between arbitrary nodesa, b
and the directed paira:b
creates two value-type layers:- each node is mapped to all its outgoing edges,
- each edge is mapped to the respective edge value.
In short,
graph[a]
provides a collection of edges originating ata
, whilegraph[a:b]
provides the specific edge value froma
tob
.Note
Many interfaces return the rich
Edge
type for its added usability. To access an edge value, usingslice
such asgraph[a:b]
is sufficient, however.Similar to
Mappings
, nodes are the primary keys of aGraph
. As a result, the container interfaces, such asiter
andlen
, operate on nodes. In general, nodes can be of arbitrary type as long as they are hashable.By default, edges in a
Graph
are directed and unique: The edges represented bygraph[a:b]
andgraph[b:a]
are separate with opposite direction. Each edge is unique, i.e. there is only one edgegraph[a:b]
. A loop is represented by the edgegraph[a:a]
. The edge entities stored in the graph may be arbitrary objects.As such, the interface of
Graph
defaults to describing a directed graph. However, other types of graph can be expressed as well. These generally do not form separate types in term of implementation.Multigraphs allow for multiple edges between pairs of nodes. In this case, all edge values are containers (such as
list
orset
) of arbitrary size. Whether aGraph
is a graph of containers or a multigraph depends on the context.Undirected Graphs do not distinguish between
graph[a:b]
andgraph[b:a]
. This can be enforced by symmetry of edge values, which guarantees thatgraph[a:b] == graph[b:a]
always applies.-
g.undirected
Indicates whether
Graph
g
is guaranteed to be undirected, having only symmetric edge values. IfTrue
,g[a:b] is g[b:a]
for any nodesa
andb
ing
; the graph enforces this, e.g.g[a:b] = c
impliesg[b:a] = c
. IfFalse
, symmetric edges are allowed but not enforced.Read-only unless explicitly indicated otherwise.
There are several ways to initialise a new graph; their main difference is which element types are left empty.
-
Graph()
Create a new empty graph. No nodes, edges or values are filled in.
-
Graph(graph)
Create a new graph with all nodes, edges and values of
graph
. The resulting graph is a shallow copy ofgraph
- the identity of elements is preserved.
-
Graph(a, b, c, ...)
-
Graph([a, b, c, ...])
-
Graph({a, b, c, ...})
-
Graph(<iterable for a, b, c, ...>)
Create a new graph with nodes
a
,b
,c
,d
, and so on. No edges or values are created explicitly.
-
Graph({a: {b: ab_edge, c: ...}, b: {a: ab_edge, ...}})
-
Graph({a: AdjacencyList({b: ab_edge, c: ...}), b: AdjacencyList(...), ...})
Create a new graph with nodes
a
,b
,c
, and so on. Initialize edges tograph[a:b] = ab_edge
,graph[b:a] = ba_edge
, and so on.
Note
If only a single argument is provided, graph and mapping initialization is preferred over iterable initialisation. To initialize a graph with a graph or mapping as the sole node, wrap it in an iterable, e.g.
Graph([graph])
.All implementations of this ABC guarantee the following operators:
-
bool(g)
Whether there are any nodes in the graph
g
.
-
len(g)
Return the number of nodes in the graph
g
.
-
g[a:b]
Return the value of the edge between nodes
a
andb
. RaisesEdgeError
if no edge is defined for the nodes. Undirected graphs guaranteeg[a:b] == g[b:a]
.
-
g[a:b] = value
Set the value of the edge between nodes
a
andb
tovalue
for graphg
.
-
del g[a:b]
Remove the edge and value between nodes
a
andb
fromg
. RaisesEdgeError
if the edge is not in the graph.
-
g[a]
Return the edges between nodes
a
and any other node as anAdjacencyList
corresponding to{b: ab_edge, c: ac_edge, ...}
. RaisesNodeError
ifa
is not ing
.
-
g[a] = True
-
g.add(a)
Add the node
a
to graphg
if it does not exist. Do not add, remove or modify existing edges. Graphs for which edges are computed, not set, may create them implicitly.Changed in version 0.3.0: Added
g[a] = True
, deprecatedg[a] = a
andg[a] = None
.
-
g[a] = {}
-
g[a] = AdjacencyList()
Add the node
a
to graphg
if it does not exist. Remove any existing edges originating ata
from graphg
.
-
g[a] = {b: ab_edge, c: ac_edge, ...}
-
g[a] = AdjacencyList(b=ab_edge, c=c_edge)
Add the node
a
to graphg
if it does not exist. Set the value of the edge between nodesa
andb
toab_edge
, betweena
andc
toac_edge
, and so on. Remove any other edge froma
. RaisesNodeError
if any ofb
,c
, etc. are not ing
.
-
del g[a]
Remove the node
a
and all its edges fromg
. RaisesNodeError
if the node is not in the graph.
-
a in g
Return
True
ifg
has a nodea
, elseFalse
.
-
Edge[a:b] in g
-
Edge(a, b) in g
Return
True
ifg
has an edge from nodea
tob
, elseFalse
.
-
iter(g)
Return an iterator over the nodes in
g
.
In addition, several methods are provided. While methods and operators for retrieving data must be implemented by all subclasses, methods for modifying data may not be applicable to certain graphs.
-
add
(item)¶ Safely add a node or edge to the graph, without modifying existing edges
If a node is not part of the graph, it is added without any explicit edges. If a edge is not part of the graph, its value is set to
True
.Note
Graphs which compute edges may implicitly create new edges if
node
is new to the graph.
-
clear
()¶ Remove all elements from this graph
-
copy
()¶ Return a shallow copy of this graph
-
discard
(item)¶ Remove a node or edge from the graph if it is a member
Parameters: item – node or edge to discard from the graph
-
edges
()¶ Return a new view of the graph’s edges
Returns: view of the graph’s edges Return type: EdgeView
-
get
(item, default=None)¶ Return the value for node or edge
item
if it is in the graph, else default. Ifdefault
is not given, it defaults toNone
, so that this method never raises aNodeError
orEdgeError
.Parameters: - item – node or edge to look up in the graph
- default – default to return if
item
is not in the graph
-
items
()¶ Return a new view of the graph’s edges and their values
Returns: view of the graph’s edges and their values Return type: ItemView
-
nodes
()¶ Return a new view of the graph’s nodes
Returns: view of the graph’s nodes Return type: NodeView
-
undirected
= False¶ whether this graph is undirected, having only symmetric edges
-
class
graphi.abc.
GraphView
(graph)¶ Bases:
_abcoll.Sized
Dynamic view on the content of a
Graph
View objects represent a portion of the content of a graph. A view allows to work with its scope without copying the viewed content. It is dynamic, meaning that any changes to the graph are reflected by the view.
Each view works only on its respective portion of the graph. For example,
edge in nodeview
will always returnFalse
.-
len(graphview)
Return the number of nodes, node pairs or edges in the graph.
-
x in graphview
Return
True
if x is a node, node pair or edge of the graph.
-
iter(graphview)
Return an iterator over the nodes, node pairs or edges in the graph.
Each view strictly defines the use of nodes, edges or values. As such, edges are safely represented as a tuple of start and end node.
-
undirected
¶
-
-
class
graphi.abc.
ItemView
(graph)¶ Bases:
graphi.abc.GraphView
View on the edges and values in a graph
Represents edges and their value as a
tuple
of(tail, head, value)
. For example, the edgegraph[a:b] = c
corresponds to the item(a, b, c)
.
-
exception
graphi.abc.
NodeError
¶ Bases:
exceptions.Exception
Graph node not found
-
class
graphi.abc.
NodeView
(graph)¶ Bases:
graphi.abc.GraphView
View on the nodes of a graph
-
class
graphi.abc.
ValueView
(graph)¶ Bases:
graphi.abc.GraphView
View on the values of edges in a graph