Algorithms for graphs¶
Undirected edgeweighted graph corresponding to an adjacency matrix. 


Labelises graph vertices according to the given graph cut. 

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

Compute the line graph of an undirected graph. 

Creates a graph from vertex coordinates. 

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

Extract a subgraph of the input graph. 

Subdominant ultrametric of the given edge weighted graph. 

Adjacency matrix corresponding to an undirected edgeweighted graph (the result is thus symmetric). 

adjacency_matrix_2_undirected_graph
(adjacency_matrix, non_edge_value=0)[source]¶ Undirected edgeweighted 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:
adjacency_matrix – Input adjacency matrix (A 2d symmetric square matrix)
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 edgeweights 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 edgetovertex 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
isTrue
; 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 arrayedge_indices
.If
spanning
isFalse
, the subgraph may contain less vertices than the input graph. In such case, the optional array result \(vertex\_map\) (returned ifreturn_vertex_map
isTrue
) 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) >>> graph.add_edges(np.arange(5), np.arange(1, 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
isTrue
, 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 edgeweighted graph (the result is thus symmetric).
As the given graph is not necessarily complete, nonexisting 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())
ifNone
)non_edge_value – Value used to represent edges that are not in the input graph (must be 0 if
sparse
isTrue
)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 given dissimilarity measure. The result is thus a saliency map: new edge weights such that any upper thresholding of the edge weights will produce graph cut.
In the case of an edge weighted undirected graph, the value of the subdominant ultrametric \(u(e_{xy})\) on the edge \(e_{xy}\) is given by the minmax distance between \(x\) and \(y\):
\[u(e_{xy}) = min_{p \in P_{xy}} max_{e \in p} w(e)\]where \(P_{xy}\) is the set of all paths between \(x\) and \(y\).
This function is a morphological opening: it is increasing, idempotent and antiextensive (with respect to
edge_weights
).Complexity: \(\mathcal{O}(n*log(n))\) with \(n\) the number of edges in the graph.
 Example:
>>> graph = hg.get_4_adjacency_graph((3, 3)) >>> edge_weights = np.asarray((2, 3, 9, 5, 10, 1, 5, 8, 2, 2, 4, 3)) >>> hg.ultrametric_open(graph, edge_weights) array([2, 3, 9, 3, 9, 1, 4, 3, 2, 2, 4, 3])
 Parameters:
graph – Input graph
edge_weights – Graph edge weights (disimilarity measure)
 Returns:
edge weights corresponding to the subdominant ultrametric