Adding and removing vertices and edges

Building up and tearing down a graph’s structure can be achieved by methods on the graph, vertex, and edge classes. These methods work for directed and undirected graphs.

Graph

The graph class provides methods for adding and removing vertices and edges.

`add_vertex`	Add a vertex to the graph
`add_edge`	Add an edge to the graph (base class method)
`remove_edge`	Remove an edge from the graph
`remove_vertex`	Remove a vertex, and all its edges, from the graph

Vertex

The vertex class provides methods for connecting a vertex to another vertex and for removing a vertex, and its edges, from the graph.

`connect`	Connect two vertices with an edge
`remove`	Remove this vertex, and all its edges, from its graph

Edge

The edge class provides methods for attaching an edge to a pair of vertices and for removing an edge from the graph. They are described on the Edges & Vertices page.

`connect`	Attach this edge to a pair of vertices
`remove`	Remove this edge from its graph

Details

Graph.add_vertex(coord=None, name=None)[source]

Add a vertex to the graph

Parameters:

coord (array-like or Vertex subclass, optional) – coordinate for an embedded graph, or an existing vertex (an instance of this graph’s vertex_class, not belonging to a graph) to add as-is, defaults to None
name (str, optional) – name of vertex, defaults to “#i”

Raises:

TypeError – coord is a Vertex that is not an instance of this graph’s vertex_class
ValueError – the name is already used by another vertex in the graph, or coord is a vertex that already belongs to a graph
ValueError – the graph was constructed with dim, and coord is given but its length doesn’t match

Returns:

the added vertex

Return type:

Vertex subclass

This is a graph-centric way of creating a vertex.

g.add_vertex() creates a new vertex with optional coord and name.
g.add_vertex(v) takes an instance of this graph’s vertex_class (by default any Vertex) and adds it to the graph.

If the vertex has no name and name is None give it a default name #N where N is the number of vertices, or the next integer above it that is not already used by a name in the graph.

Names are unique within a graph, since they are how g[name] finds a vertex, and a vertex belongs to one graph at a time.

Changed in version 1.0: Adding a vertex whose name is already used raises ValueError. It used to replace the earlier vertex in the name table, leaving it in the graph but unreachable by name. A default name could also clash with an existing one after a vertex had been removed.

The vertex is placed into the graph’s vertex dictionary with a key equal to its name.

>>> from pgraph import UGraph, Vertex
>>> g = UGraph()
>>> v1 = g.add_vertex(coord=[0,0])
>>> repr(v1)
'Vertex[#0, coord=(0, 0)]'
>>> print(v1)
[#0]
>>> print(v1.name)
#0
>>> v2 = g.add_vertex(Vertex(coord=[1,1], name='v2'))
>>> print(v2.name)
v2
>>> g['v2']
Vertex[v2, coord=(1, 1)]

If the graph was constructed with a required dim (see Graph), every embedded vertex must have a coordinate of exactly that length – adding one of the wrong length raises ValueError:

>>> from pgraph import UGraph
>>> g = UGraph(dim=6)
>>> v1 = g.add_vertex(coord=[0, 0, 0, 0, 0, 0], name='pose1')
>>> print(v1)
[pose1]

Note

This single implementation, shared by UGraph and DGraph, is parameterized by the graph’s vertex_class rather than duplicated per subclass – see Object lifecycle and graph-membership policy for why that matters.

Seealso:: vertex_copy()

Graph.add_edge(v1, v2=None, **kwargs)[source]

Add an edge to the graph (base class method)

Parameters:

v1 (Vertex subclass, str or Edge) – first vertex (start if a directed graph), or an existing edge that already carries its two vertices
v2 (Vertex subclass or str, optional) – second vertex (end if a directed graph), must be omitted if v1 is an edge
kwargs (Any) – optional arguments to pass to Vertex.connect, not allowed if v1 is an edge

Raises:

TypeError – v1 or v2 is of the wrong type, or v2, cost or data is given along with an edge
ValueError – the edge has no vertices, or the vertices do not belong to this graph

Returns:

edge

Return type:

Edge

This is a graph-centric way of creating an edge. The alternative is the connect method of a vertex.

g.add_edge(v1, v2) creates an edge between a vertex pair and adds it to the graph.
g.add_edge(e) takes an edge, or an instance of an Edge subclass, that was constructed with its two vertices and adds it to the graph, just as g.add_vertex(v) takes an existing vertex.

>>> from pgraph import UGraph
>>> g = UGraph()
>>> v1 = g.add_vertex(coord=[0,0], name='v1')
>>> v2 = g.add_vertex(coord=[1,1], name='v2')
>>> v3 = g.add_vertex(coord=[2,2], name='v3')
>>> e = g.add_edge(v1, v2)
>>> print(e)
Edge{[v1] -- [v2], cost=1.414}
>>> e2 = g.add_edge('v2', 'v3', cost=99)
>>> print(e2)
Edge{[v2] -- [v3], cost=99}

Note that at line 9 the vertices are specified by their string names.

Adding an instance of a user-defined Edge subclass:

>>> from pgraph import UGraph, Edge
>>> class MyEdge(Edge):
...     pass
>>> g = UGraph()
>>> v1 = g.add_vertex(coord=[0,0], name='v1')
>>> v2 = g.add_vertex(coord=[1,1], name='v2')
>>> e = g.add_edge(MyEdge(v1, v2, data="a road"))
>>> print(type(e).__name__, e.data)
MyEdge a road

Note

Vertices have coordinates and the edge cost defaults to the distance between them, but if the vertices have no coordinates the edge cost must be set explicitly, otherwise it will be None and path planning will fail with a ValueError.

Note

To supply an edge that does not yet have vertices use g.add_edge(v1, v2, edge=e) or e.connect(v1, v2).

Seealso:: add_vertex() Edge.connect() Vertex.connect()

Graph.remove_edge(edge)[source]

Remove an edge from the graph

Parameters:: edge (Edge) – edge to remove
Raises:: ValueError – edge does not belong to this graph
Return type:: None

The edge is removed from this graph’s own edge collection and from the edge lists of its connected vertices, and edge.v1/edge.v2 are cleared to None.

Warning

The connectivity of the network may be changed.

>>> from pgraph import UGraph
>>> g = UGraph()
>>> v1 = g.add_vertex(coord=[0,0], name='v1')
>>> v2 = g.add_vertex(coord=[1,1], name='v2')
>>> e = g.add_edge(v1, v2)
>>> g.remove_edge(e)
>>> print(g)
UGraph: 2 vertices, 0 edges, 2 components

Note

A directed edge is tracked only by its source vertex’s edge list, not its target’s (see Vertex.edges), so membership is checked per endpoint rather than assumed for both – removing a directed edge from an undirected-only implementation would otherwise raise ValueError on the target side.

Seealso:: remove_vertex() Edge.remove()

Graph.remove_vertex(vertex)[source]

Remove a vertex, and all its edges, from the graph

Parameters:: vertex (Vertex) – vertex to remove
Raises:: ValueError – vertex does not belong to this graph
Return type:: None

Every edge touching vertex – incoming or outgoing – is removed via remove_edge(), then the vertex itself is removed.

Warning

The connectivity of the network may be changed.

>>> from pgraph import UGraph
>>> g = UGraph()
>>> v1 = g.add_vertex(coord=[0,0], name='v1')
>>> v2 = g.add_vertex(coord=[1,1], name='v2')
>>> g.add_edge(v1, v2)
Edge{[v1] -- [v2], cost=1.414}
>>> g.remove_vertex(v2)
>>> print(g)
UGraph: 1 vertex, 0 edges, 1 component

Note

This scans the graph’s own edge set for edges touching vertex, rather than iterating vertex.edges() – for a DGraph vertex that only ever reports outgoing edges (see Vertex.edges), so incoming edges would otherwise be missed and left dangling.

Seealso:: remove_edge() Vertex.remove()

Graph.remove(x)[source]

Remove element from graph (deprecated)

Parameters:: x (Edge or Vertex subclass) – element to remove from graph
Raises:: TypeError – unknown type
Return type:: None

Deprecated since version use: remove_edge() or remove_vertex() instead – this dispatched on type(x) to two operations with very different blast radii (detach one edge, vs. cascade-remove everything touching a vertex) hidden behind one ambiguous name.

Seealso:: remove_edge() remove_vertex()

Vertex.connect(dest, edge=None, cost=None, data=None)[source]

Connect two vertices with an edge

Parameters:

dest (Vertex subclass) – The vertex to connect to
edge (Edge subclass, optional) – Use this as the edge object, otherwise a new object of the graph’s Graph.edge_class is created from the vertices being connected, and the cost and data parameters, defaults to None
cost (float, optional) – the cost to traverse this edge, defaults to None
data (Any, optional) – reference to arbitrary data associated with the edge, defaults to None

Raises:

ValueError – either vertex has not been added to a graph, the vertices belong to different graphs, or edge already connects other vertices
TypeError – edge is not an instance of the graph’s Graph.edge_class

Returns:

the edge connecting the vertices

Return type:

Edge

v1.connect(v2) connects vertex v1 to vertex v2.

Note

In an undirected graph the edge is recorded in the edge list of both vertices, so it is found from either end. In a directed graph it is recorded as leaving this, the start, vertex and entering dest.
A supplied edge built without vertices has its v1 and v2 set to the vertices being connected. One built with vertices must agree with them: in either order if undirected, exactly self then dest if directed.
Both vertices must already have been added to the same graph, e.g. via Graph.add_vertex().

>>> from pgraph import UGraph
>>> g = UGraph()
>>> v1 = g.add_vertex(coord=[0,0], name='v1')
>>> v2 = g.add_vertex(coord=[1,1], name='v2')
>>> e = v1.connect(v2, cost=1.414)
>>> print(e)
Edge{[v1] -- [v2], cost=1.414}

Seealso:: Edge() Edge.connect()

Vertex.remove()[source]

Remove this vertex, and all its edges, from its graph

Raises:: ValueError – the vertex is not connected to a graph

v.remove() removes v, and every edge touching it (incoming or outgoing), from its graph. The Vertex object itself is not deleted.

Note

This is a thin convenience wrapper around Graph.remove_vertex().

Return type:: None

>>> from pgraph import UGraph
>>> g = UGraph()
>>> v1 = g.add_vertex(coord=[0,0], name='v1')
>>> v2 = g.add_vertex(coord=[1,1], name='v2')
>>> g.add_edge(v1, v2)
Edge{[v1] -- [v2], cost=1.414}
>>> v2.remove()
>>> print(g)
UGraph: 1 vertex, 0 edges, 1 component

Seealso:: Graph.remove_vertex() Edge.remove()