# Algorithms for graphs¶

 Undirected edge-weighted graph corresponding to an adjacency matrix. graph_cut_2_labelisation(graph, edge_weights) Labelises graph vertices according to the given graph cut. labelisation_2_graph_cut(graph, vertex_labels) Determines the graph cut that corresponds to a given labeling of the graph vertices. line_graph(graph) Compute the line graph of an undirected graph. make_graph_from_points(X[, graph_type, …]) Creates a graph from vertex coordinates. minimum_spanning_tree(graph, edge_weights) Computes the minimum spanning tree of the given edge weighted graph with Kruskal’s algorithm. subgraph(graph, edge_indices[, spanning, …]) Extract a subgraph of the input graph. ultrametric_open(graph, edge_weights) Subdominant ultrametric of the given edge weighted graph. undirected_graph_2_adjacency_matrix(graph[, …]) Adjacency matrix corresponding to an undirected edge-weighted graph (the result is thus symmetric).
adjacency_matrix_2_undirected_graph(adjacency_matrix, non_edge_value=0)[source]

Undirected edge-weighted graph corresponding to an adjacency matrix.

Adjacency matrix entries which are equal to non_edge_value are not considered to be part of the graph.

Parameters

• non_edge_value – Value used to represent non existing edges in the adjacency matrix

Returns

a pair (UndirectedGraph, ndarray) representing the graph and its edge_weights (Concept CptEdgeWeightedGraph)

graph_cut_2_labelisation(graph, edge_weights)[source]

Labelises graph vertices according to the given graph cut.

Each edge having a non zero value in the given edge_weights are assumed to be part of the cut.

Parameters
• graph – Input graph

• edge_weights – Weights on the edges of the graph

Returns

A labelisation of the graph vertices

labelisation_2_graph_cut(graph, vertex_labels)[source]

Determines the graph cut that corresponds to a given labeling of the graph vertices.

The result is a weighting of the graph edges where edges with a non zero weight are part of the cut.

Parameters
• graph – input graph

• vertex_labels – Weights on the vertices of the graph

Returns

graph edge-weights representing the equivalent cut

line_graph(graph)[source]

Compute the line graph of an undirected graph.

The line graph $$LG$$ of an undirected graph $$G$$ is a graph such that:

• each vertex of $$LG$$ represents an edge of $$G$$: the $$i$$-th vertex of $$LG$$ corresponds to the $$i$$-th edge of $$G$$; and

• two vertices $$x$$ and $$y$$ of $$LG$$ are adjacent if their corresponding edges in $$G$$ share a common extremity. Formally, if $$x$$ represents the edge $$\{i, j \}$$ and if $$y$$ represents the edge $$\{k, j \}$$, then the edge $$\{x, y\}$$ belongs to $$LG$$ if $$\{i, j \} \cap \{k, j \} \neq \emptyset$$.

The line graph is also known as: the covering graph, the derivative, the edge-to-vertex dual, the conjugate, the representative graph, the edge graph, the interchange graph, the adjoint graph, or the derived graph.

Parameters

graph – input graph

Returns

the line graph of the input graph

make_graph_from_points(X, graph_type='knn+mst', symmetrization='max', **kwargs)[source]

Creates a graph from vertex coordinates.

The argument graph_type selects the graph creation methods. Possible values are:

• "complete": creates the complete graph

• "knn": creates a $$k$$-nearest neighbor graph, the parameter $$k$$ can be controlled with the extra parameter ‘n_neighbors’ (default value 5). The resulting graph may have several connected components.

• "knn+mst" (default): creates a $$k$$-nearest neighbor graph and add the edges of an mst of the complete graph. This method ensures that the resulting graph is connected. The parameter $$k$$ can be controlled with the extra parameter ‘n_neighbors’ (default value 5).

• "delaunay": creates a graph corresponding to the Delaunay triangulation of the points (only works in low dimensions).

The weight of an edge $$\{x,y\}$$ is equal to the Euclidean distance between $$x$$ and $$y$$: $$w(\{x,y\})=\|X[x, :] - X[y, :]\|$$.

$$K$$-nearest neighbor based graphs are naturally directed, the argument symmetrization enables to chose a symmetrization strategy. Possible values are:

• "min": an edge $$\{x,y\}$$ is created if there both arcs $$(x,y)$$ and $$(y,x)$$ exist. Its weight is given by the minimum weight of the two arcs.

• "max": an edge $$\{x,y\}$$ is created if there is any of the two arcs $$(x,y)$$ and $$(y,x)$$ exists. Its weight is given by the weight of the existing arcs (if both arcs exists they necessarily have the same weight).

This method is not suited for large set of points.

Parameters
• X – A 2d array of vertex coordinates

• graph_type"complete", "knn", "knn+mst" (default), or "delaunay"

• symmetrization“min” or "max"

• kwargs – extra args depends of chosen graph type

Returns

a graph and its edge weights

minimum_spanning_tree(graph, edge_weights)[source]

Computes the minimum spanning tree of the given edge weighted graph with Kruskal’s algorithm.

If the input graph is not connected, the result is indeed a minimum spanning forest.

Complexity: $$\mathcal{O}(n*log(n))$$ with $$n$$ the number of edges in the graph

Parameters
• graph – Input graph

• edge_weights – Graph edge weights

Returns

a minimum spanning tree of the input edge weighted graph (Concept CptMinimumSpanningTree)

subgraph(graph, edge_indices, spanning=True, return_vertex_map=False)[source]

Extract a subgraph of the input graph. Let $$G=(V,E)$$ be the graph graph and let $$E^*$$ be a subset of $$E$$. The subgraph of $$G$$ induced by $$E^*$$ is equal to:

• $$(V, E^*)$$ is spanning is True; and

• $$(\bigcup E^*, E^*)$$ otherwise (the set of vertices of the subgraph is equal to the set of vertices present at an extremity of an edge in $$E^*$$).

The array edge_indices contains the indices of the edges in the set $$E^*$$. The edges in the subgraph are in the same order as the edges in the array edge_indices.

If spanning is False, the subgraph may contain less vertices than the input graph. In such case, the optional array result $$vertex\_map$$ (returned if return_vertex_map is True) indicates for each vertex $$i$$ of the subgraph, its corresponding index in the input graph.

Example
>>> # linear graph with 6 vertices
>>> graph = hg.UndirectedGraph(6)
>>>
>>> # select edges (4, 5), (0, 1), and (3, 4), note that vertex 2 is not in any edge
>>> edge_indices = np.asarray((4, 0, 3))
>>> subgraph, vertex_map = hg.subgraph(graph, edge_indices, spanning=False, return_vertex_map=True)
>>>
>>> subgraph.num_vertices()
5
>>> vertex_map
[0 1 3 4 5]
>>> subgraph.edge_list()
([3 0 2], [4 1 3])
>>> vertex_map
[0 1 3 4 5]

Parameters
• graph – input graph.

• edge_indices – an array of edge indices of the input graph.

• spanning – if True, the subgraph has the same vertex set as the input graph.

• return_vertex_map – if True, also returns an array mapping each vertex of the current to its corresponding vertex in the input graph.

Returns

a subgraph and, if return_vertex_map is True, a vertex map

undirected_graph_2_adjacency_matrix(graph, edge_weights=None, non_edge_value=0, sparse=True)[source]

Adjacency matrix corresponding to an undirected edge-weighted graph (the result is thus symmetric).

As the given graph is not necessarily complete, non-existing edges will receive the value non_edge_value in the adjacency matrix.

Parameters
• graph – Input graph

• edge_weights – Graph edge weights (default to np.ones(graph.num_edges()) if None)

• non_edge_value – Value used to represent edges that are not in the input graph (must be 0 if sparse is True)

• sparse – if True the result will be a sparse matrix in the csr format (requires Scipy to be installed)

Returns

A 2d symmetric square matrix

ultrametric_open`(graph, edge_weights)[source]

Subdominant ultrametric of the given edge weighted graph.

The subdominant ultrametric relative to a given dissimilarity measure (here the graph edge weights) is defined as the largest ultrametric smaller than the dissimilarity measure.

In the case of an edge weighted undirected graph, the value of the subdominant ultrametric on the edge $$e_{xy}$$ is given by the min-max distance between $$x$$ and $$y$$.

Complexity: $$\mathcal{O}(n*log(n))$$ with $$n$$ the number of edges in the graph

Parameters
• graph – Input graph

• edge_weights – Graph edge weights

Returns

edge weights corresponding to the subdominant ultrametric