 |
STAG C++
2.0.0
Spectral Toolkit of Algorithms for Graphs
|
|
STAG C++
2.0.0
Spectral Toolkit of Algorithms for Graphs
|
#include <graph.h>
The core object used to represent graphs for use with the library.
Graphs are always constructed from sparse matrices, and this is the internal representation used as well. Vertices of the graph are always referred to by their unique integer index. This index corresponds to the position of the vertex in the stored adjacency matrix of the graph.
This class supports graphs with positive edge weights. Self-loops are permitted.
Public Member Functions | |
| Graph (const SprsMat &matrix) | |
| Graph (std::vector< StagInt > &outerStarts, std::vector< StagInt > &innerIndices, std::vector< StagReal > &values) | |
| const SprsMat * | adjacency () const |
| const SprsMat * | laplacian () |
| const SprsMat * | normalised_laplacian () |
| const SprsMat * | signless_laplacian () |
| const SprsMat * | normalised_signless_laplacian () |
| const SprsMat * | degree_matrix () |
| const SprsMat * | inverse_degree_matrix () |
| const SprsMat * | lazy_random_walk_matrix () |
| StagReal | total_volume () |
| StagReal | average_degree () |
| StagInt | number_of_vertices () const |
| StagInt | number_of_edges () const |
| void | add_edge (StagInt i, StagInt j, StagReal w) |
| void | remove_edge (StagInt i, StagInt j) |
| bool | has_self_loops () const |
| bool | is_connected () |
| Graph | subgraph (std::vector< StagInt > &vertices) |
| Graph | disjoint_union (Graph &other) |
| StagReal | degree (StagInt v) override |
| StagInt | degree_unweighted (StagInt v) override |
| std::vector< edge > | neighbors (StagInt v) override |
| std::vector< StagInt > | neighbors_unweighted (StagInt v) override |
| std::vector< StagReal > | degrees (std::vector< StagInt > vertices) override |
| std::vector< StagInt > | degrees_unweighted (std::vector< StagInt > vertices) override |
| bool | vertex_exists (StagInt v) override |
 Public Member Functions inherited from stag::LocalGraph | |
| virtual StagReal | degree (StagInt v)=0 |
| virtual StagInt | degree_unweighted (StagInt v)=0 |
| virtual std::vector< edge > | neighbors (StagInt v)=0 |
| virtual std::vector< StagInt > | neighbors_unweighted (StagInt v)=0 |
| virtual std::vector< StagReal > | degrees (std::vector< StagInt > vertices)=0 |
| virtual std::vector< StagInt > | degrees_unweighted (std::vector< StagInt > vertices)=0 |
| virtual bool | vertex_exists (StagInt v)=0 |
| virtual | ~LocalGraph ()=default |
|
explicit |
Create a graph from an Eigen matrix.
The provided matrix should correspond either to the adjacency matrix or Laplacian matrix of the graph. STAG will automatically detect whether the provided matrix is an adjacency matrix or a Laplacian matrix.
The provided matrix must be symmetric, and may include self-loops.
| matrix | the sparse eigen matrix representing the adjacency matrix or Laplacian matrix of the graph. |
| domain_error | if the provided matrix is not symmetric |
| stag::Graph::Graph | ( | std::vector< StagInt > & | outerStarts, |
| std::vector< StagInt > & | innerIndices, | ||
| std::vector< StagReal > & | values | ||
| ) |
Create a graph from raw arrays describing a CSC sparse matrix.
To use this constructor, you should understand the CSC sparse matrix format. Note that this library uses the ColMajor format from the Eigen library. For more information, refer to the Eigen Documentation.
| outerStarts | the indices of the start of each row in the CSR matrix |
| innerIndices | the column indices of each non-zero element in the matrix |
| values | the values of each non-zero element in the matrix |
| const SprsMat * stag::Graph::adjacency | ( | ) | const |
Return the sparse adjacency matrix of the graph.
| const SprsMat * stag::Graph::laplacian | ( | ) |
Return the Laplacian matrix of the graph.
The Laplacian matrix is defined by
\[ L = D - A \]
where \(D\) is the diagonal matrix of vertex degrees (stag::Graph::degree_matrix) and A is the adjacency matrix of the graph (stag::Graph::adjacency).
| const SprsMat * stag::Graph::normalised_laplacian | ( | ) |
Return the normalised Laplacian matrix of the graph.
The normalised Laplacian matrix is defined by
\[ \mathcal{L} = D^{-1/2} L D^{-1/2} \]
where \(D\) is the diagonal matrix of vertex degrees (stag::Graph::degree_matrix) and \(L\) is the Laplacian matrix of the graph (stag::Graph::laplacian).
| const SprsMat * stag::Graph::signless_laplacian | ( | ) |
Return the signless Laplacian matrix of the graph.
The signless Laplacian matrix is defined by
\[ J = D + A \]
where \(D\) is the diagonal matrix of vertex degrees (stag::Graph::degree_matrix) and A is the adjacency matrix of the graph (stag::Graph::adjacency).
| const SprsMat * stag::Graph::normalised_signless_laplacian | ( | ) |
Return the normalised signless Laplacian matrix of the graph.
The normalised signless Laplacian matrix is defined by
\[ \mathcal{J} = D^{-1/2} J D^{-1/2} \]
where \(D\) is the diagonal matrix of vertex degrees (stag::Graph::degree_matrix) and \(J\) is the signless Laplacian matrix of the graph (stag::Graph::signless_laplacian).
| const SprsMat * stag::Graph::degree_matrix | ( | ) |
The degree matrix of the graph.
The degree matrix is an \(n \times n\) matrix such that each diagonal entry is the degree of the corresponding node.
| const SprsMat * stag::Graph::inverse_degree_matrix | ( | ) |
The inverse degree matrix of the graph.
The inverse degree matrix is an \(n \times n\) matrix such that each diagonal entry is the inverse of the degree of the corresponding node, or 0 if the node has degree 0.
| const SprsMat * stag::Graph::lazy_random_walk_matrix | ( | ) |
The lazy random walk matrix of the graph.
The lazy random walk matrix is defined to be
\[ \frac{1}{2} I + \frac{1}{2} A D^{-1} \]
where \(I\) is the identity matrix, \(A\) is the graph adjacency matrix and \(D\) is the degree matrix of the graph.
| StagReal stag::Graph::total_volume | ( | ) |
The total volume of the graph.
The volume is defined as the sum of the node degrees.
| StagReal stag::Graph::average_degree | ( | ) |
The average degree of the graph.
This is defined as the sum of the node degrees divided by the number of nodes.
| StagInt stag::Graph::number_of_vertices | ( | ) | const |
The number of vertices in the graph.
| StagInt stag::Graph::number_of_edges | ( | ) | const |
The number of edges in the graph.
This is defined based on the number of non-zero elements in the adjacency matrix, and ignores the weights of the edges.
Add an edge to the graph.
The edge goes from node i to node j, and is added with weight w. If there is already an edge from i to j, then w is added to its weight.
If either of \(i\) or \(j\) are larger than the number of nodes in the graph, the graph is resized to have enough nodes.
| i | |
| j | |
| w |
Remove an edge from the graph.
Remove any edge between nodes \(i\) and \(j\).
| i | |
| j |
| bool stag::Graph::has_self_loops | ( | ) | const |
Returns a boolean indicating whether this graph contains self loops.
| bool stag::Graph::is_connected | ( | ) |
Returns a boolean indicating whether the graph is connected.
The running time of this method is \(O(m)\), where \(m\) is the number of edges in the graph.
Construct and return a subgraph of this graph.
Note that the vertex indices will be changed in the subgraph.
| vertices | the vertices in the induced subgraph |
Construct and return the disjoint union of this graph and another.
The disjoint union of two graphs \(G\) and \(H\) is a graph containing \(G\) and \(H\) as disconnected subgraphs.
| other | the other graph to be combined with this one |
Given a vertex v, return its weighted degree.
A self-loop of weight \(1\) contributes \(2\) to the vertex's degree.
Implements stag::LocalGraph.
Given a vertex v, return its unweighted degree. That is, the number of neighbors of v, ignoring the edge weights.
Implements stag::LocalGraph.
Given a vertex v, return a vector of edges representing the neighborhood of v.
The returned edges will all have the ordering (v, x) such that edge.v = v.
| v | an int representing some vertex in the graph |
Implements stag::LocalGraph.
Given a vertex v, return a vector containing the neighbors of v.
The weights of edges to the neighbors are not returned by this method.
| v | an int representing some vertex in the graph |
Implements stag::LocalGraph.
Given a list of vertices, return the degrees of each vertex in the list.
Providing a method for computing the degrees 'in bulk' increases the efficiency of algorithms on graphs which are not stored directly in memory.
| vertices | a vector of ints representing the vertices to be queried. |
Implements stag::LocalGraph.
|
overridevirtual |
Given a list of vertices, return their unweighted degrees.
| vertices | a vector of ints representing the vertices to be queried. |
Implements stag::LocalGraph.
|
overridevirtual |
Given a vertex ID, returns true or false to indicate whether the vertex exists in the graph.
| v | the vertex index to check |
Implements stag::LocalGraph.
1.9.6