Graph analysis

Querying structure – counts, adjacent vertices, incident edges, degree, connectivity, distance – for directed and undirected graphs. See Path planning for finding paths between vertices, and Transformations to matrix representations for the matrix and dot forms of the whole graph.

A vertex is queried in two complementary ways: by the vertices it is adjacent to, and by the edges incident on it. For the adjacent vertices adjacent() is the canonical name; for a directed graph successors() is the same list under its directed name, and predecessors() is the vertices with an edge to the vertex. The edges are out_edges() and in_edges(), and incidences() pairs each adjacent vertex with the edge that leads to it. edgeto() is the edge to one adjacent vertex, the cheapest if there are parallel edges, and edges_to() lists all of them.

Graph

The size and kind of the graph

`n`	Number of vertices
`ne`	Number of edges
`nc`	Number of components
`directed`	Test if the graph is directed
`edges`	All edges in the graph, in the order they were added

Structure and connectivity

`iscyclic`	Test if graph is cyclic
`component`	All vertices in specified graph component
`samecomponent`	Test if vertices belong to same graph component
`connectivity`	Graph connectivity
`average_degree`	Average degree of the graph

Geometry and consistency

For a graph whose vertices have coordinates, coordinates() is the matrix of them, one column per vertex. closest() finds the nearest vertex to a point, near() the vertices within a distance of a point and within() the vertices inside a box. Passing the result of the last to subgraph() gives the part of the graph in a region, without the edges that cross its border, and a boolean mask computed from the coordinates selects in the same way.

These are a single pass over the vertices. For a large graph that is queried often, build_kdtree() builds an index that closest() and near() then use, which needs scipy and is for the built-in metrics.

`coordinates`	Coordinates of all the vertices as a matrix
`closest`	Vertex closest to point
`near`	Vertices within a distance of a point
`within`	Vertices inside a box
`build_kdtree`	Build a spatial index of the vertices, used by `closest()` and `near()`
`subgraph`	Subgraph induced by a set of vertices
`validate`	Check that the graph's records agree with each other

The matrices of a graph (adjacency(), degree(), incidence(), laplacian(), distance()) are in Transformations to matrix representations.

Vertex

Identity and position

`name`	Name of the vertex
`label`	Number of the graph component that contains the vertex
`x`	The x-coordinate of an embedded vertex
`y`	The y-coordinate of an embedded vertex
`z`	The z-coordinate of an embedded vertex

Adjacent vertices

`adjacent`	Vertices adjacent to this vertex
`isadjacent`	Test if a vertex is adjacent to this vertex
`successors`	Vertices that this vertex has an edge to
`predecessors`	Vertices that have an edge to this vertex

Note

neighbours() and neighbors() are the same method as adjacent(), and isneighbour() and isneighbor() the same as isadjacent(). They are spelling variants, not deprecated.

Incident edges

`edges`	The edges at the vertex, in the order they were connected
`out_edges`	The edges leaving the vertex
`in_edges`	The edges entering the vertex
`incidences`	Adjacent vertices paired with the edges that lead to them
`edgeto`	The edge from this vertex to an adjacent vertex
`edges_to`	All the edges from this vertex to another vertex

Degree

`degree`	Degree of vertex
`in_degree`	Number of edges entering the vertex
`out_degree`	Number of edges leaving the vertex

Distance

`distance`	Distance from vertex to point
`heuristic_distance`	Heuristic distance to another vertex
`closest`	Return the closest vertex to this vertex

Edge

An Edge is described in full on Edges & Vertices. The attributes and methods used to query one are

`v1`	First vertex of the edge, the start vertex for a directed edge
`v2`	Second vertex of the edge, the end vertex for a directed edge
`endpoints`	The two vertices of this edge
`next`	Return other end of an edge

and every edge also has cost and data attributes.

Details

property Graph.n: int

Number of vertices

Returns:: Number of vertices
Return type:: int

>>> from pgraph import UGraph
>>> g = UGraph()
>>> g.add_vertex(name='v1')
Vertex[v1, coord=(?)]
>>> g.add_vertex(name='v2')
Vertex[v2, coord=(?)]
>>> print(g.n)
2

property Graph.ne: int

Number of edges

Returns:: Number of vertices
Return type:: int

>>> from pgraph import UGraph
>>> g = UGraph()
>>> v1 = g.add_vertex(name='v1')
>>> v2 = g.add_vertex(name='v2')
>>> g.add_edge(v1, v2)
Edge{[v1] -- [v2], cost=None}
>>> print(g.ne)
1

property Graph.nc: int

Number of components

Returns:: Number of components
Return type:: int

Number of components in the graph. Components are labeled from 0 to g.nc-1.

For a directed graph the components are weakly connected: the direction of the edges is ignored, so two vertices are in the same component if there is a path between them that may run against the arrows. A graph with no vertices has no components.

Changed in version 1.0: Does not hang. For many directed graphs, the smallest being the 4-cycle, the algorithm of 0.6.5 never finished, which also stopped component(), samecomponent() and plot().

>>> from pgraph import UGraph
>>> g = UGraph()
>>> v1 = g.add_vertex(name='v1')
>>> v2 = g.add_vertex(name='v2')
>>> v3 = g.add_vertex(name='v3')
>>> g.add_edge(v1, v2)
Edge{[v1] -- [v2], cost=None}
>>> print(g.nc)
2

Note

A lazy approach is used, and if a connectivity changing operation has been performed since the last call, the graph coloring algorithm is run which is potentially expensive for a large graph.

Seealso:: component() samecomponent()

property Graph.directed: bool

Test if the graph is directed

Returns:: True for a DGraph, False for a UGraph
Return type:: bool

An undirected edge is recorded at both of its vertices, and is followed in either direction. A directed edge is recorded as leaving its start vertex and entering its end vertex.

>>> from pgraph import Graph
>>> Graph().directed
False
>>> Graph(directed=True).directed
True

Seealso:: UGraph DGraph

Graph.edges()[source]

All edges in the graph, in the order they were added

Returns:: All edges in the graph
Return type:: list of Edge references

The edges are in the order they were added to the graph. This is a new list, so it can be modified or sorted without affecting the graph, and edges can be removed from the graph while iterating over it.

We can iterate over all edges in the graph by:

for e in g.edges():
    print(e)

and select one by index, for example the second edge added is g.edges()[1].

Note

Like Vertex.edges() this is a list, but where that lists the edges attached to one vertex, this lists every edge in the graph once. A self-loop is one edge here, but appears twice in the Vertex.edges() of an undirected vertex because it has two ends there.

Changed in version 1.0: Returns a list in order of addition. In 0.6.5 this was the graph’s own set, with no defined order, although the documentation said list.

>>> 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}
>>> print(g.edges())
[Edge{[v1] -- [v2], cost=1.414}]

Seealso:: Vertex.edges() ne

Graph.iscyclic()[source]

Test if graph is cyclic

Returns:: true if the graph contains at least one cycle
Return type:: bool

For an undirected graph this is a simple count: a forest (acyclic) has exactly n - nc edges, one per component-connecting edge with no redundancy, so any excess indicates a cycle. This is O(1) given n(), ne() and nc(), which are already cached.

For a directed graph this runs Kahn’s algorithm: repeatedly remove vertices with no remaining incoming edges. If every vertex can eventually be removed, the graph is a DAG (acyclic); if some are never freed, they form a cycle. This is O(V+E), using vertices’ outgoing edges via Vertex.adjacent() the same way path_BFS() and friends do.

>>> from pgraph import UGraph
>>> g = UGraph()
>>> v1 = g.add_vertex(name='v1')
>>> v2 = g.add_vertex(name='v2')
>>> v3 = g.add_vertex(name='v3')
>>> g.add_edge(v1, v2)
Edge{[v1] -- [v2], cost=None}
>>> g.add_edge(v2, v3)
Edge{[v2] -- [v3], cost=None}
>>> print(g.iscyclic())
False
>>> g.add_edge(v3, v1)
Edge{[v3] -- [v1], cost=None}
>>> print(g.iscyclic())
True

Note

A self-loop is a cycle of length one, so it makes either kind of graph cyclic. Two parallel edges between the same pair of vertices are a cycle in an undirected graph, but a repeated arrow in a directed graph is not.

Note

A matrix-based test also exists in theory – a digraph is acyclic iff its adjacency matrix is nilpotent (all eigenvalues zero) – but that needs an O(N^3) eigendecomposition plus a floating-point zero-tolerance judgement call, to answer a question Kahn’s algorithm answers exactly with integers in O(V+E). Not used here for that reason.

Seealso:: adjacency()

Graph.component(c)[source]

All vertices in specified graph component

Parameters:: c (int) – component index
Returns:: vertices belonging to component c
Return type:: list of Vertex subclass

graph.component(c) is a list of all vertices in graph component c.

>>> from pgraph import UGraph
>>> g = UGraph()
>>> v1 = g.add_vertex(name='v1')
>>> v2 = g.add_vertex(name='v2')
>>> v3 = g.add_vertex(name='v3')
>>> g.add_edge(v1, v2);
Edge{[v1] -- [v2], cost=None}
>>> print(g)
UGraph: 3 vertices, 1 edge, 2 components
>>> print(g.component(0))
[Vertex[v1, coord=(?)], Vertex[v2, coord=(?)]]

Seealso:: nc samecomponent()

Graph.samecomponent(v1, v2)[source]

Test if vertices belong to same graph component

Parameters:

v1 (Vertex subclass) – vertex
v2 (Vertex subclass) – vertex

Returns:

true if vertices belong to same graph component

Return type:

bool

Test whether vertices belong to the same component. A component is a set of vertices that are connected by a path of edges, ignoring their direction, so for a directed graph this does not mean that there is a path from one to the other: a -> c <- b is one component, but there is no path from a to b.

>>> from pgraph import UGraph
>>> g = UGraph()
>>> v1 = g.add_vertex(name='v1')
>>> v2 = g.add_vertex(name='v2')
>>> v3 = g.add_vertex(name='v3')
>>> g.add_edge(v1, v2)
Edge{[v1] -- [v2], cost=None}
>>> print(g.samecomponent(v1, v2))
True
>>> print(g.samecomponent(v1, v3))
False

Seealso:: component() nc

Graph.connectivity(vertices=None)[source]

Graph connectivity

Parameters:: vertices (iterable of Vertex subclass, optional) – vertices to report connectivity for, defaults to all vertices in the graph
Returns:: a list with the number of edges per vertex
Return type:: list

This is the Vertex.degree of each vertex: the number of edge ends at it, which is the number of edges connected to it except that a self-loop has two ends and so counts twice. For a directed graph it counts the edges entering the vertex as well as those leaving.

Changed in version 1.0: For a DGraph this counted only the edges leaving each vertex. Use [v.out_degree for v in g] for the previous values.

The average vertex connectivity is:

mean(g.connectivity())

and the minimum vertex connectivity is:

min(g.connectivity())

>>> from pgraph import UGraph
>>> import numpy as np
>>> g = UGraph()
>>> for i in range(5):
...     g.add_vertex(np.random.rand(2));
Vertex[#0, coord=(0.744, 0.7207)]
Vertex[#1, coord=(0.5883, 0.3748)]
Vertex[#2, coord=(0.09699, 0.4609)]
Vertex[#3, coord=(0.6158, 0.2589)]
Vertex[#4, coord=(0.02597, 0.001061)]
>>> for i, j in [(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (3, 4)]:
...     g.add_edge(g[i], g[j]);
Edge{[#0] -- [#1], cost=0.3793}
Edge{[#0] -- [#2], cost=0.6972}
Edge{[#0] -- [#3], cost=0.4793}
Edge{[#1] -- [#2], cost=0.4988}
Edge{[#1] -- [#3], cost=0.1192}
Edge{[#3] -- [#4], cost=0.6437}
>>> c = g.connectivity()
>>> print(c)
[3, 3, 2, 3, 1]

Note

This is the diagonal of degree(). Parallel edges are counted individually.

Seealso:: degree() average_degree() Vertex.degree

Graph.average_degree()[source]

Average degree of the graph

Returns:: average degree
Return type:: float

Average degree is \(2 E / N\) where \(E\) is the total number of edges and \(N\) is the number of vertices, for an undirected or a directed graph. It is the mean of Vertex.degree, and every edge has two ends, so the degrees sum to \(2 E\).

Parallel edges and self-loops are each counted as one edge in \(E\); a self-loop contributes 2 to the degree sum.

Changed in version 1.0: For a DGraph this was \(E / N\), the mean out-degree (which equals the mean in-degree). It is now \(2 E / N\), the mean of the degree, which is twice the old value. Use g.ne / g.n for the previous number.

>>> from pgraph import UGraph
>>> g = UGraph()
>>> v1 = g.add_vertex(name='v1')
>>> v2 = g.add_vertex(name='v2')
>>> v3 = g.add_vertex(name='v3')
>>> g.add_edge(v1, v2);
Edge{[v1] -- [v2], cost=None}
>>> g.add_edge(v2, v3);
Edge{[v2] -- [v3], cost=None}
>>> print(g.average_degree())
1.3333333333333333

Seealso:: degree() connectivity() Vertex.degree

Graph.coordinates()[source]

Coordinates of all the vertices as a matrix

Returns:: coordinates, one column per vertex in the order they were added
Return type:: ndarray(dim, n)
Raises:: ValueError – the coordinates of two vertices differ in length

Column i is the coordinate of g[i], the same order as the rows and columns of adjacency(). A vertex that has no coordinate has a column of NaN, so the matrix always has one column per vertex. The number of rows is dim if the graph was given one, otherwise the length of the first coordinate, and 0 if no vertex has one. Elements are float.

The result is a view of a new array that has one row per vertex, so the coordinate of each vertex is contiguous in memory and C[:, i] is a contiguous slice, while a row such as C[0] is strided. Use numpy.ascontiguousarray() if you need the rows to be contiguous.

Note

This is a snapshot, made each time: changing it does not move the vertices, and moving a vertex does not change a matrix that was already returned.

With NumPy this selects vertices in a single operation, as within() and near() do, or it can be given to a spatial index of your own.

>>> from pgraph import UGraph
>>> g = UGraph()
>>> for i in range(3):
...     g.add_vertex(coord=[i, 10 * i])
Vertex[#0, coord=(0, 0)]
Vertex[#1, coord=(1, 10)]
Vertex[#2, coord=(2, 20)]
>>> g.coordinates()
array([[ 0.,  1.,  2.],
       [ 0., 10., 20.]])

Seealso:: within() near() closest() adjacency()

Graph.closest(coord)[source]

Vertex closest to point

Parameters:: coord (ndarray(n)) – coordinates of a point
Returns:: closest vertex and its distance, or (None, inf) if no vertex in the graph has a coordinate
Return type:: Vertex subclass or None, float

Returns the vertex closest to the given point. Distance is computed according to the graph’s metric. Vertices without a coordinate (coord is None) are skipped – they have no position to compare.

This is a pass over the vertices, unless a spatial index has been built with build_kdtree() and is still valid.

>>> from pgraph import UGraph
>>> g = UGraph()
>>> v1 = g.add_vertex(coord=[0,0], name='v1')
>>> v2 = g.add_vertex(coord=[10,10], name='v2')
>>> vertex, d = g.closest([1, 1])
>>> print(vertex, d)
[v1] 1.4142135623730951

Seealso:: metric() near() build_kdtree()

Graph.near(coord, radius)[source]

Vertices within a distance of a point

Parameters:

coord (ndarray(n)) – coordinates of a point
radius (float) – greatest distance, inclusive

Raises:

ValueError – radius is negative

Returns:

the vertices within radius of the point with their distances, nearest first

Return type:

list of (Vertex subclass, float)

Distance is computed according to the graph’s metric, as it is by closest(), of which this is the generalization to every vertex within a radius. Vertices without a coordinate are skipped, and vertices at equal distance are in the order of the graph.

For the built-in metrics the distance to every vertex is found in one operation on coordinates(), or by the spatial index if build_kdtree() was called; a metric of your own is applied to each vertex in turn.

>>> from pgraph import UGraph
>>> g = UGraph()
>>> for i in range(5):
...     g.add_vertex(coord=[i, 0], name=f"v{i}")
Vertex[v0, coord=(0, 0)]
Vertex[v1, coord=(1, 0)]
Vertex[v2, coord=(2, 0)]
Vertex[v3, coord=(3, 0)]
Vertex[v4, coord=(4, 0)]
>>> [(v.name, d) for v, d in g.near([2.2, 0], 1.5)]
[('v2', 0.20000000000000018), ('v3', 0.7999999999999998), ('v1', 1.2000000000000002)]

Seealso:: closest() within() metric() build_kdtree()

Graph.within(box)[source]

Vertices inside a box

Parameters:: box (ndarray(2,n)) – lower and upper corners of the box
Raises:: ValueError – box is not 2 x n, its upper corner is below its lower corner in some dimension, or the coordinates of the vertices do not have n elements
Returns:: the vertices inside the box, in the order of the graph
Return type:: list of Vertex subclass

The first row of box is the lower corner, the second row the upper corner, so in two dimensions it is [[xmin, ymin], [xmax, ymax]]. The box is closed: a vertex on its boundary is inside. Vertices without a coordinate are skipped, as they are by closest().

The test is made for all the vertices at once on coordinates(). Together with subgraph() it selects the part of an embedded graph in a region

>>> from pgraph import UGraph
>>> g = UGraph()
>>> for i in range(5):
...     g.add_vertex(coord=[i, i], name=f"v{i}")
Vertex[v0, coord=(0, 0)]
Vertex[v1, coord=(1, 1)]
Vertex[v2, coord=(2, 2)]
Vertex[v3, coord=(3, 3)]
Vertex[v4, coord=(4, 4)]
>>> g.within([[1, 1], [3, 3]])
[Vertex[v1, coord=(1, 1)], Vertex[v2, coord=(2, 2)], Vertex[v3, coord=(3, 3)]]
>>> g.subgraph(g.within([[1, 1], [3, 3]]))
UGraph:
  v1 at [1 1] component=0
  v2 at [2 2] component=1
  v3 at [3 3] component=2

Seealso:: near() closest() subgraph() coordinates()

Graph.build_kdtree()[source]

Build a spatial index of the vertices, used by closest() and near()

Raises:

ValueError – the metric is not one of the built-in "L1", "L2" or "SE2", or "SE2" and the coordinates are not 3 elements, or no vertex has a coordinate
ImportError – scipy is not installed

Finding the nearest vertex to a point is a pass over all the vertices, which is the cost of a query on a large graph that is queried often. A k-d tree answers in a time that grows more slowly, at the cost of building it once. closest() and near() use the index if it has been built, and fall back to the pass over the vertices if it has not or if the graph has changed.

The index is for the built-in metrics "L1", "L2" and "SE2" (with any weight, see SE2Metric), and results are the same as without it, except that when two vertices are exactly the same distance the one returned may differ.

Warning

The index is dropped when a vertex is added or removed or when vertex.coord is assigned (including +=), and closest() is then correct but slow, until it is built again. It cannot see a coordinate that is changed in place, vertex.coord[0] = x. Do not change vertices in place after building, or build again.

The index is not copied or pickled with the graph.

Note

This needs scipy. pgraph does not list it as a dependency and imports it only when this method is called, but spatialmath-python, which pgraph does depend on, installs it.

Seealso:: closest() near() coordinates()
Return type:: None

Graph.subgraph(vertices)[source]

Subgraph induced by a set of vertices

Parameters:

vertices (iterable of Vertex subclass or str, or ndarray(n) of bool) – vertices of this graph, or their names, or a boolean mask with one element per vertex

Raises:

ValueError – a vertex is not in this graph, or a mask is not the length of the number of vertices
KeyError – a name is not that of a vertex in this graph
TypeError – an item is neither a vertex nor a string

Returns:

a new graph of the same kind

Return type:

Graph

The new graph has the given vertices and every edge of this graph that has both its end vertices among them. An edge that has one end outside is removed, so the edges that cross the border of a region are dropped. Parallel edges and loops are kept.

Like copy() the new graph is independent of this one: its vertices and edges are new objects that keep their class, name, coordinate, cost and any attributes that were added, and the graph keeps its metric, heuristic and vertex and edge classes. They are in the order of this graph, however vertices was ordered. Names are kept, so the vertex g[name] has its counterpart h[name].

>>> from pgraph import UGraph
>>> g = UGraph()
>>> v = [g.add_vertex(coord=[i, 0], name=f"v{i}") for i in range(4)]
>>> for i in range(3):
...     g.add_edge(v[i], v[i + 1])
Edge{[v0] -- [v1], cost=1}
Edge{[v1] -- [v2], cost=1}
Edge{[v2] -- [v3], cost=1}
>>> h = g.subgraph([v[1], v[2]])
>>> print(h)
UGraph: 2 vertices, 1 edge, 1 component
>>> h.edges()
[Edge{[v1] -- [v2], cost=1}]

It is a single pass over the graph. The vertices might be a component, the vertices that satisfy a test, or those in a region of an embedded graph from within().

A boolean mask, such as the result of a comparison on coordinates(), selects the vertices by their position in the graph, the True elements being kept:

h = g.subgraph(g.coordinates()[0] > 0)   # the vertices with x > 0

The mask must be of boolean type (a list of bool also works) and of length g.n. A vector of 0 and 1 of integer type is not accepted, since it could as well be a list of indices.

Seealso:: copy() within() component()

Graph.validate(embedded=False)[source]

Check that the graph’s records agree with each other

Parameters:: embedded (bool) – also report a vertex that has no coordinate, defaults to False
Returns:: a description of each inconsistency found, empty if the graph is consistent
Return type:: list of str

A graph keeps the same facts in several places: its set of edges, each vertex’s list of outgoing edges (and, for a directed graph, of incoming ones), each edge’s two vertices, each vertex’s pointer back to its graph, and the table of vertex names. The library keeps them in step, so a graph built and edited through the public methods is always valid. This is a check for tests, for debugging, and for code that reaches into the internals.

It does not change the graph, and takes time proportional to the number of vertices plus edges. It reports every inconsistency, not only the first.

The checks are:

the vertex list holds only vertices, once each, and the edge set holds only edges
every edge in the graph has two vertices, both in this graph, and is an instance of edge_class
every vertex points back at this graph, is an instance of vertex_class, is in the name table under its own name, and has a coordinate of the required length if dim was given
every coordinate is a finite one-dimensional numeric vector, and if dim was not given they all have the same length
with embedded=True, every vertex has a coordinate. A graph with no coordinates is valid, but one that is half embedded rarely is
every entry of the name table is a vertex of this graph and is filed under its own name
each edge is in the right vertex lists, the right number of times: both ends for an undirected edge (twice at one vertex for a self-loop), the source’s outgoing and the target’s incoming list for a directed edge
no vertex list holds an edge that is not in the graph

>>> from pgraph import UGraph
>>> g = UGraph()
>>> v1 = g.add_vertex(name='v1')
>>> v2 = g.add_vertex(name='v2')
>>> g.add_edge(v1, v2)
Edge{[v1] -- [v2], cost=None}
>>> print(g.validate())
[]

Seealso:: remove_edge() remove_vertex()

property Vertex.name: str | None

Name of the vertex

Returns:: the name
Return type:: str or None

The name is the vertex’s key in its graph: g[name] and name in g look it up. A vertex that is not in a graph can be given any name, or none. For one that is in a graph:

assigning a new name updates the graph’s name table, so the vertex is then found under the new name and not the old
a name already used by another vertex in the graph raises ValueError and changes nothing
the name cannot be cleared

Changed in version 1.0: Renaming a vertex in a graph used to leave the graph’s name table stale, so lookups by the new name failed.

Seealso:: Graph.add_vertex()

property Vertex.label: int | None

Number of the graph component that contains the vertex

Returns:: component number, counted from 0, or None if the vertex is not in a graph
Return type:: int or None

Assigned by the graph, which finds its components when this is read after the graph has changed, as it does for Graph.nc, Graph.component() and Graph.samecomponent(). The numbering is by the first vertex of each component, in the order the vertices were added. It is read-only.

Changed in version 1.0: Read-only. It was a plain attribute, but it is computed from the graph’s structure and meaningless to assign. Reading it finds the components; in 0.6.5 it was None until something else had.

Seealso:: Graph.nc Graph.component()

property Vertex.x: float

The x-coordinate of an embedded vertex

Raises:: ValueError – the vertex has no coordinate
Returns:: The x-coordinate
Return type:: float

>>> from pgraph import Vertex
>>> v = Vertex(coord=[1,2], name='v1')
>>> print(v.x)
1

property Vertex.y: float

The y-coordinate of an embedded vertex

Raises:: ValueError – the vertex has no coordinate
Returns:: The y-coordinate
Return type:: float

>>> from pgraph import Vertex
>>> v = Vertex(coord=[1,2], name='v1')
>>> print(v.y)
2

property Vertex.z: float

The z-coordinate of an embedded vertex

Raises:: ValueError – the vertex has no coordinate
Returns:: The z-coordinate
Return type:: float

>>> from pgraph import Vertex
>>> v = Vertex(coord=[1,2,3], name='v1')
>>> print(v.z)
3

Vertex.adjacent()[source]

Vertices adjacent to this vertex

Returns:: the vertices at the far end of this vertex’s edges
Return type:: list of Vertex subclass

v.adjacent() is a list of the vertices that this vertex is joined to by an edge. “Adjacent” is the graph-theory term, and it is the relation that Graph.adjacency() tabulates: row i of the adjacency matrix is non-zero exactly at the columns of the vertices returned by g[i].adjacent().

Note

For a directed graph these are the vertices at the head of the edges leaving this vertex, the successors.
There is one entry per edge, so a vertex joined by k parallel edges appears k times. In an undirected graph a self-loop lists the vertex itself twice, once for each end.
neighbours and neighbors are aliases, the same method under the British and American spellings, and are not deprecated.

>>> 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')
>>> g.add_edge(v1, v2)
Edge{[v1] -- [v2], cost=1.414}
>>> g.add_edge(v1, v3)
Edge{[v1] -- [v3], cost=2.828}
>>> print(v1.adjacent())
[Vertex[v2, coord=(1, 1)], Vertex[v3, coord=(2, 2)]]

Seealso:: isadjacent() successors() predecessors() incidences() out_edges() edges() Graph.adjacency()

Vertex.isadjacent(vertex)[source]

Test if a vertex is adjacent to this vertex

Parameters:: vertex (Vertex subclass) – vertex reference
Returns:: true if vertex is adjacent
Return type:: bool

For a directed graph this is true only if there is an edge from self to vertex.

isneighbour and isneighbor are aliases.

>>> 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')
>>> g.add_edge(v1, v2)
Edge{[v1] -- [v2], cost=1.414}
>>> print(v1.isadjacent(v2))
True
>>> print(v1.isadjacent(v3))
False

Seealso:: adjacent()

Vertex.successors()[source]

Vertices that this vertex has an edge to

Returns:: the vertices at the head of the outgoing edges
Return type:: list of Vertex subclass

This is adjacent(), under its directed-graph name.

Seealso:: predecessors() adjacent() incidences() out_edges()

Vertex.predecessors()[source]

Vertices that have an edge to this vertex

Returns:: the vertices at the tail of the incoming edges
Return type:: list of Vertex subclass

There is one entry per edge, so a vertex joined by k parallel edges appears k times. For an undirected graph this is adjacent().

>>> from pgraph import DGraph
>>> g = DGraph()
>>> 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')
>>> g.add_edge(v1, v3)
Edge{[v1] -> [v3], cost=2.828}
>>> g.add_edge(v2, v3)
Edge{[v2] -> [v3], cost=1.414}
>>> print(v3.predecessors())
[Vertex[v1, coord=(0, 0)], Vertex[v2, coord=(1, 1)]]

Seealso:: successors() adjacent() in_edges() in_degree

Vertex.edges()[source]

The edges at the vertex, in the order they were connected

Returns:: the edges at this vertex
Return type:: list of Edge

For a directed graph these are the edges leaving this vertex. For an undirected graph they are the edges incident on it, whichever end it is. A self-loop in an undirected graph is listed twice, once for each end.

The list is a new one on every call, in the order the edges were connected, so changing it does not change the graph, and edges can be removed from the graph while iterating over it. Use Graph.remove_edge() to remove one.

>>> 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}
>>> print(v1.edges())
[Edge{[v1] -- [v2], cost=1.414}]

Seealso:: out_edges() in_edges() adjacent() incidences() edges_to() degree Graph.edges()

Vertex.out_edges()[source]

The edges leaving the vertex

Returns:: the outgoing edges, in the order they were connected
Return type:: list of Edge

This is a new list, and is the same as edges(): for an undirected graph every incident edge is outgoing.

Seealso:: in_edges() edges() adjacent() successors() incidences() edges_to() out_degree

Vertex.in_edges()[source]

The edges entering the vertex

Returns:: the incoming edges, in the order they were connected
Return type:: list of Edge

This is a new list. For an undirected graph every incident edge is incoming, so it equals edges().

Seealso:: out_edges() edges() predecessors() in_degree

Vertex.incidences()[source]

Adjacent vertices paired with the edges that lead to them

Returns:: a (vertex, edge) pair for each edge leaving this vertex, in the order the edges were connected
Return type:: list of (Vertex subclass, Edge)

v.incidences() is adjacent() and out_edges() taken together: the first element of each pair is the vertex at the far end of the edge, the second is the edge itself, so its Edge.cost and Edge.data are at hand. It is equivalent to:

list(zip(v.adjacent(), v.out_edges()))

but is built in a single pass, which is what the path-planning methods want when they expand a vertex.

Note

In graph-theory terms adjacent() is a vertex’s adjacency list, out_edges() its incidence list, and this is the two joined.
For a directed graph the pairs are for the edges leaving this vertex. The ones entering it are in_edges(), and the vertices at their tails are predecessors().
There is one pair per edge, so parallel edges to the same vertex give repeated vertices with different edges, and an undirected self-loop gives the pair twice, once for each end.

>>> 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')
>>> g.add_edge(v1, v2, cost=1.5)
Edge{[v1] -- [v2], cost=1.5}
>>> g.add_edge(v1, v3, cost=2.5)
Edge{[v1] -- [v3], cost=2.5}
>>> for vertex, edge in v1.incidences():
...     print(vertex.name, edge.cost)
v2 1.5
v3 2.5

Seealso:: adjacent() isadjacent() successors() out_edges() in_edges() predecessors() edgeto() edges_to() edges() edgeto() degree Graph.adjacency()

Vertex.edgeto(dest)[source]

The edge from this vertex to an adjacent vertex

Parameters:: dest (Vertex subclass) – an adjacent vertex
Raises:: ValueError – dest is not adjacent to this vertex
Returns:: the edge from this vertex to dest
Return type:: Edge

Note

For a directed graph dest must be at the arrow end of the edge
If there are parallel edges to dest the cheapest is returned (the first, if none of them has a cost)

>>> 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, cost=1.414)
Edge{[v1] -- [v2], cost=1.414}
>>> print(v1.edgeto(v2))
Edge{[v1] -- [v2], cost=1.414}

Seealso:: edges_to() incidences() adjacent()

Vertex.edges_to(dest)[source]

All the edges from this vertex to another vertex

Parameters:: dest (Vertex subclass) – the vertex at the far end
Returns:: every edge from this vertex to dest, in the order they were connected, which is empty if there are none
Return type:: list of Edge

This is how to see parallel edges. edgeto() returns the one edge that a path would use, the cheapest, whereas this returns them all.

Note

For a directed graph only the edges leaving this vertex for dest are included, so a.edges_to(b) and b.edges_to(a) are different lists
For an undirected graph the edges are found from either end, whichever vertex they were connected from
A self-loop is listed once, although its vertex holds it twice (see edges())
Unlike edgeto(), there being no edge is not an error, the list is empty
The list is a new one, so changing it does not change the graph

>>> 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, cost=3)
Edge{[v1] -- [v2], cost=3}
>>> g.add_edge(v1, v2, cost=1)
Edge{[v1] -- [v2], cost=1}
>>> print(v1.edges_to(v2))
[Edge{[v1] -- [v2], cost=3}, Edge{[v1] -- [v2], cost=1}]
>>> print(v1.edgeto(v2))
Edge{[v1] -- [v2], cost=1}

Seealso:: edgeto() edges() out_edges() incidences() adjacent()

property Vertex.degree: int

Degree of vertex

Returns:: degree of the vertex
Return type:: int

The number of edge ends at this vertex: the edges leaving it plus the edges entering it, so a self-loop counts twice. The degrees of all the vertices of a graph sum to twice its number of edges.

For an undirected graph this is the number of incident edges. For a directed graph it is in_degree + out_degree.

Changed in version 1.0: For a DGraph this used to count only the edges leaving the vertex. It is now the graph-theory degree, in plus out. Use out_degree for the previous value.

>>> from pgraph import DGraph
>>> g = DGraph()
>>> 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')
>>> g.add_edge(v1, v2)
Edge{[v1] -> [v2], cost=1.414}
>>> g.add_edge(v1, v3)
Edge{[v1] -> [v3], cost=2.828}
>>> g.add_edge(v3, v1)
Edge{[v3] -> [v1], cost=2.828}
>>> print(v1.degree, v1.in_degree, v1.out_degree)
3 1 2

For graphs with parallel edges or loops

Every edge is counted, so k parallel edges to the same vertex add k. A self-loop adds 2, for both kinds of graph: it has two ends.

Seealso:: in_degree out_degree edges() Graph.degree() Graph.connectivity()

property Vertex.in_degree: int

Number of edges entering the vertex

Returns:: in-degree of the vertex
Return type:: int

For an undirected graph every incident edge both leaves and enters, so this equals degree.

Seealso:: out_degree degree in_edges()

property Vertex.out_degree: int

Number of edges leaving the vertex

Returns:: out-degree of the vertex
Return type:: int

For an undirected graph every incident edge both leaves and enters, so this equals degree.

Seealso:: in_degree degree out_edges()

Vertex.distance(coord)[source]

Distance from vertex to point

Parameters:: coord (ndarray(n) or Vertex) – coordinates of the point
Returns:: distance
Return type:: float

Distance is computed according to the graph’s metric. The vertex must belong to a graph, since the metric is a property of the graph, not the vertex.

>>> from pgraph import UGraph
>>> g = UGraph()
>>> v1 = g.add_vertex(coord=[0,0], name='v1')
>>> v2 = g.add_vertex(coord=[3,4], name='v2')
>>> print(v1.distance(v2))
5.0

Seealso:: Graph.metric

Vertex.heuristic_distance(v2)[source]

Heuristic distance to another vertex

Parameters:: v2 (Vertex subclass) – the other vertex
Returns:: heuristic distance between this vertex and v2
Return type:: float

Distance is computed according to the graph’s heuristic, see Graph.heuristic(). The vertex must belong to a graph, since the heuristic is a property of the graph, not the vertex.

>>> from pgraph import UGraph
>>> g = UGraph()
>>> v1 = g.add_vertex(coord=[1, 2], name='v1')
>>> v2 = g.add_vertex(coord=[4, 3], name='v2')
>>> print(v1.heuristic_distance(v2))
3.1622776601683795

Seealso:: distance() Graph.heuristic()

Vertex.closest()[source]

Return the closest vertex to this vertex

Returns:: closest vertex and its distance
Return type:: Vertex subclass or None, float

Equivalent to self._graph.closest(self.coord). The vertex must belong to a graph, since closest() searches that graph’s other vertices.

>>> 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,3], name='v3')
>>> v4 = g.add_vertex(coord=[4,3], name='v4')
>>> print(v1.closest())
(Vertex[v1, coord=(0, 0)], 0.0)

Seealso:: Graph.closest()