Base
This module contains the base GraphElement, Node, Edge,
and Graph implementations for Graphine.
The API’s are located at GraphElement, Node, Edge and Graph
You can find the source code for this module here.
This module contains the base GraphElement, Node, Edge,
and Graph implementations for Graphine, an easy-to-use,
easy-to-extend Graph library.
Graphs generated using this representation can have
directed, undirected, and parallel edges.
Interface summary
To create a new Graph:
>>> from graph.base import Graph >>> g = Graph()
Adding elements to a Graph
In Graphine, each element has a unique hashable name and
data attributes. If you do not provide a name at
instantiation time, one will be autogenerated, but it is
strongly recommended that you provide one, since element
comparisons (and therefore graph comparisons) are done by
name.
To add a node:
>>> node_1 = g.add_node() >>> node_1 Node(name=3081985036)
To add a named node:
>>> node_2 = g.add_node("bob") >>> node_2 Node(name=bob)
To add a node with data attributes:
>>> node_3 = g.add_node("dan", weight=5) >>> node_3 Node(name="dan", weight=5)
Since Edges connect nodes, it makes sense that instantiating
an edge will require exactly two nodes as arguments. These
can be specified either by name or by element reference.
To add an edge:
>>> edge_1 = g.add_edge(node_1, node_2) >>> edge_1 Edge(name=3081985196)
To add a named edge:
>>> edge_2 = g.add_edge(node_2, node_3, "2->3") >>> edge_2 Edge(name=2->3)
To add an edge by node name:
>>> edge_3 = g.add_edge("bob", "dan", "bob->dan") Edge(name=bob->dan)
Notice that edges can have data attributes as well:
>>> edge_4 = g.add_edge("dan", "dan", "dan->dan", weight=5) >>> edge_4 Edge(name=dan->dan, weight=5)
You can access these attributes using normal attribute notation:
>>> edge_4.weight 5 >>> edge_4.weight = 7 >>> edge_4.weight 7
We can also add attributes on the fly:
>>> edge_4.color = "blue" >>> edge_4 Edge(name=dan->dan, weight=7, color=blue)
Edges also permit a keyword argument is_directed, which indicates
whether that edge should be directed or undirected. Its default
value is True, meaning that the edge will be directed from the
first node provided to the second node provided.
>>> edge_5 = g.add_edge(node_1, node_2, "1->2", is_directed=False) Edge(name=1->2)
In the next section, you will learn how to use the properties
of Nodes and Edges to verify this.
In addition to adding nodes and edges, you can remove them.
This can also be done either by name or by element reference.
To remove nodes:
>>> g.remove_node(node_1) Node(name=3081985036)
To remove nodes by name:
>>> g.remove_node("bob") Node(name=bob)
And edges:
>>> g.remove_edge(edge_4)
Note that removing one or more of an Edge’s endpoints will
remove that edge as well, so the following will raise KeyError:
>>> g.remove_edge(edge_4)
Navigating Graphs
In addition to storing your data, Nodes and Edges have
a few other special properties by default.
For Nodes, these properties are “incoming” and “outgoing”,
and they contain the incoming and outgoing edges attached
to that node. The “bidirectional” property is also there
in case you only want the edges which go both ways. An
additional property “edges” contains all of these elements.
For Edges, these properties are (again, by default)
“start” and “end”. Because edges can be bidirectional,
they also have an “is_directed” property, and provide
the convenience function “other_end”, which takes a
node and, if possible, returns the opposite endpoint
incident to that edge.
Let’s say we have constructed the following graph:
>>> G = Graph() >>> G.add_node("A") >>> G.add_node("B") >>> G.add_node("C") >>> G.add_edge("A", "B", "AB") >>> G.add_edge("B", "C", "BC") >>> G.add_edge("C", "A", "CA" is_directed=False)
Notice that we haven’t stored any references to our Nodes
or Edges. We can do this because the graph automatically
converts between names and elements- which is why it is so
important that names be unique within a graph.
We can get an element from that graph by name by using the
standard getitem syntax:
>>> n1 = G["A"] >>> n1 Node(name=A) >>> e1 = G["AB"] >>> e1 Edge(name=AB)
It should be noted that this also works for elements, and
can be a quick test to get an element in the given graph
equivalent to one from another graph:
>>> G[Node("A")] is n1 True
Of course, now that we have a Node and Edge we can begin
to explore the graph from those points.
To get all the outgoing edges of a particular node:
>>> n1.outgoing [Edge(name=AB)]
And to get the incoming edges:
>>> n1.incoming [Edge(name=CA)]
The same sorts of things work for the properties
“bidirectional” and “edges”.
>>> n1.bidirectional [Edge(name=CA)] >>> n1.edges [Edge(name=AB), Edge(name=CA)]
You can also directly get all the nodes adjacent to a
given node:
>>> n1.get_adjacent() [Node(name=B), Node(name=C)]
From this, we can verify the following:
>>> len(n1.get_adjacent()) 2 >>> n1.degree 2
You can combine this with Edges' “start” and “end” properties
to navigate your graph, if you know how your data is related
structurally. For example, to get the oldest outgoing edge attached
to the oldest node attached to n1, I could do the following:
>>> interesting_node = n1.outgoing[0].end.outgoing[0]
In addition to these properties, Edges provide the “other_end”
function, which takes a node and, if possible, returns the edge’s
other end. If it cannot follow the edge to a point opposite the
given node- for instance, because the edge is directed the other
way- it raises AttributeError.
>>> endpoint = e1.other_end("A") Node(name=B) >>> e1.other_end("B") ... AttributeError: Edge(name=AB) contains no endpoint opposite to Node(name=B)
You will frequently see “other_end” used in situations where it is
possible that the given edge could be either directed or undirected,
or where the orientation of a directed edge is unknown.
Of course, there are scenarios in which you don’t know how to
navigate your graph, or need to find a starting point that isn’t
easily determined based on a given element’s properties. For that,
Graph supports Node and Edge iteration for the simple cases, and
traversals and walks for more complex behavior.
To iterate over all the nodes in a graph:
>>> for node in G.nodes: >>> print(node) Node(name=C) Node(name=A) Node(name=B)
Notice that these are in no particular order- Graphs do not store
elements in a sequence, and so you should not count on them being
presented in the same order on two consecutive passes.
To do the same for edges:
>>> for edge in G.edges: >>> print(edge) Edge(name=BC) Edge(name=CA) Edge(name=AB)
If you only want certain nodes, the search functions are provided
for convenience:
>>> for node in G.search_nodes(name="A"): >>> print(node) Node(name=A)
And for edges:
>>> for edge in G.search_edges(name="CA", is_directed=False): >>> print(edge) Edge(name=CA)
In addition to the datawise and unordered views of graphs,
several methods for ordering based on structural properties
are provided. The most important of these are traversals
and walks.
Three traversals are provided by default- heuristic, depth
first, and breadth first. They are all guaranteed to only
visit a given node once, and visit nodes in a different order
based on how they are related structurally.
To do a depth first traversal:
>>> for node in g.depth_first_traversal(n1): >>> print(node) Node(name=A) Node(name=B) Node(name=C)
Note that CA is an outgoing edge of n1, but will come
after the AB edge on account of being bidirectional, and
so this ordering is guaranteed.
Breadth first traversals are similar in usage, simply
substituting “depth_first_traversal” for “breadth_first_traversal”.
Heuristic traversals are similar to both breadth first and depth
first, but require an additional callable argument. This callable
will be passed a list of unvisited nodes and should select and
remove exactly one of them to return.
For example, to navigate a graph by visiting the most
popular (ie, most incoming edges) nodes first, I could
write a getter function as follows:
>>> def get_popularity(node): >>> return len(node.incoming)
A selector function:
>>> def get_most_popular(nodes): >>> nodes.sort(nodes, key=get_popularity) >>> return nodes.pop()
And traverse the graph:
>>> for node in g.heuristic_traversal("A", get_most_popular): >>> print(node) Node(name=A) Node(name=C) Node(name=B)
Note, again, that names and elements can be used interchangably.
In contrast to the traversals, walks can visit a node or edge
more than once. They are the most flexible structural technique
provided, but also do the least hand-holding of any of the
mechanisms provided, so check your assumptions carefully before
using an unlimited walk on a graph whose properties you are
unsure of.
The walks are implemented as wrapped generators, with each step
yielding a set of nodes (for walk_nodes) or edges (for walk_edges)
that are potentially “next” in terms of adjacency. The application
should select one of those and use send() to send it back. As an
example, we can implement an endless B-C-A-B loop as follows:
>>> w = G.walk_nodes("A") >>> for adjacent in w: ... w.send(adjacent[0])
The usage for walk_edges is identical, excepting that it accepts
an edge and that “adjacent” from the example would be list of
edges rather than nodes.
Finally, there is heuristic_walk, which is similar to the
heuristic_traversal in that it accepts a callable heuristic
argument and similar to the other walks in that it does similarly
little in the way of bookkeeping. To perform the walking version
of the heuristic traversal provided earlier, we could use the
same heuristic and simply do the following:
>>> for node in heuristic_walk("A", get_most_popular): ... print(node)
Inspecting Graphs
The base Graph class provides several tools for finding potentially
interesting pieces of information about your graphs.
The most straightforward of these are .order and .size, which
return the number of nodes in the graph and the number of edges in
the graph, respectively.
In addition, it has facilities to find out about the connectivity
of the given graph.
.get_connected_components() returns a list of sets of connected
verticies.
.get_strongly_connected() returns a list of sets of strongly
connected components.
.get_shortest_paths(source) returns a mapping of nodes to
a (length, [path]) pair, where path is a sequence of edges
connecting the given endpoints.
Binary Graph Operations
Three basic operations are provided for the comparison
of graphs:
union (|), which creates a new graph containing all
the nodes and edges in either of its parents,intersection (&), which creates a new graph containing
all the nodes and edges in both of its parents,difference (–), which creates a new graph containing
all the nodes and edges in the first parent but
not in the second.
For more information on the usage of these functions, consult their
individual docstrings.
