Algorithms for graphs¶
Undirected edge-weighted 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 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:
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 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
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 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())
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 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