replab.graph.Graph
: Base class for undirected and directed graphs
UndirectedGraph
: Undirected graph
DirectedGraph
: Directed graph
Bases: replab.Obj
Abstract class for immutable graphs
Vertices of the graph are numbered continuously from 1 to nVertices
Class members list
Properties
colors
– color of each all vertices; if a scalar, identical for all vertices
edges
– list of edges between vertices
nVertices
– number of vertices in the graph
weights
– weights associated to the edges; if a scalar, identical for all edges
Prettyprinting
additionalFields
– Overload of replab.Str.additionalFields
disp
– Standard MATLAB/Octave display method
headerStr
– Tiny single line description of the current object type
hiddenFields
– Overload of replab.Str.hiddenFields
longStr
– Multi-line description of the current object
shortStr
– Single line text description of the current object
Property cache
cache
– Sets the value of the designated property in the cache
cached
– Returns the cached property if it exists, computing it if necessary
cachedOrDefault
– Returns the cached property if it exists, or the provided default value if it is unknown yet
cachedOrEmpty
– Returns the cached property if it exists, or []
if it is unknown yet
inCache
– Returns whether the value of the given property has already been computed
Laws
check
– Checks the consistency of this object
checkAndContinue
– Checks the consistency of this object
laws
– Returns the laws that this object obeys
Unique ID
eq
– Equality test
id
– Returns the unique ID of this object (deprecated)
isequal
– Equality test
ne
– Non-equality test
Methods
adjacencyMatrix
– Returns the adjacency matrix of a graph
automorphismGroup
– Returns the automorphism group of the graph
computeAdjacencyMatrix
– Computes the adjacency matrix
computeHeatKernel
– Computes the heat kernel
computeLaplacian
– Computes the graph Laplacian
connectedComponents
– Returns the sets of vertices corresponding to connected components
degree
– Returns the degrees of vertex v
degrees
– Returns the degrees of all vertices
degreesSequence
– Returns the degrees sequence for all vertices
degreesSequences
– Returns the degrees sequence for all vertices
heatKernel
– The heat kernel
isBipartite
– Tests if a graph is bipartite
laplacian
– Returns the graph Laplacian
secondOrderDegree
– Returns the number of vertices at a distance 2 of vertex v
secondOrderDegrees
– Returns the number of vertices at a distance 2 of all vertices
Constructors
fromAdjacencyMatrix
– Constructs a directed graph from an adjacency matrix
fromBiadjacencyMatrix
– Constructs a directed graph from a biadjacency matrix
fromEdges
– Constructs a directed graph from a liste of edges
fromFile
– Loads a graph from a Bliss file
Inherited elements
Documentation in replab.Obj.cache()
Documentation in replab.Obj.cached()
Documentation in replab.Obj.cachedOrDefault()
Documentation in replab.Obj.cachedOrEmpty()
Documentation in replab.Obj.check()
Documentation in replab.Obj.checkAndContinue()
Documentation in replab.Str.disp()
Documentation in replab.Obj.eq()
Documentation in replab.Str.headerStr()
Documentation in replab.Obj.id()
Documentation in replab.Obj.inCache()
Documentation in replab.Obj.isequal()
Documentation in replab.Obj.laws()
Documentation in replab.Str.longStr()
Documentation in replab.Obj.ne()
Documentation in replab.Str.shortStr()
color of each all vertices; if a scalar, identical for all vertices
double (*,1)
list of edges between vertices
integer (*,2)
number of vertices in the graph
integer
weights associated to the edges; if a scalar, identical for all edges
double (*,1)
Overload of replab.Str.additionalFields
Returns the adjacency matrix of a graph
adjacency matrix
adj (double (*,*))
Example
>>> replab.UndirectedGraph.fromEdges([1 3]).adjacencyMatrix
0 0 1
0 0 0
1 0 0
Returns the automorphism group of the graph
autoG (replab.PermutationGroup
)
Computes the adjacency matrix
Computes the heat kernel
Computes the graph Laplacian
Returns the sets of vertices corresponding to connected components
For edges = [1 3] and n = 3, it returns the partition {[1 3] [2]}
Note: Graph connectedness does not take into account the graph directionality.
Partitioning of the vertices
P (replab.Partition
)
Example
>>> replab.UndirectedGraph.fromEdges([1 3]).connectedComponents
Partition '13|2'
blockIndex: [1, 2, 1]
blocks: {[1, 3], 2}
n: 3
Returns the degrees of vertex v
Returns the degrees of all vertices
Returns the degrees sequence for all vertices
Each vertex can only be counted once. For directed graphs, this corresponds to the outgoing degree sequence.
sequence of degrees
degN (integer (1,*))
Example
>>> graph = replab.DirectedGraph.fromEdges([1 3]);
>>> graph.degreesSequence(1)
1
Returns the degrees sequence for all vertices
In each sequence, a vertex can only be counted once.
list of degrees sequences
degN (integer (*,*))
Example
>>> replab.UndirectedGraph.fromEdges([1 3]).degreesSequences
1
0
1
Constructs a directed graph from an adjacency matrix
Constructs a directed graph from a biadjacency matrix
Constructs a directed graph from a liste of edges
Loads a graph from a Bliss file
The heat kernel
Evaluates the heat kernel of the graph at several times. For graphs with more than 100 vertices, an approximate heat kernel is computed.
nbTimes (integer, optional
) – the number of distinct times at
which to evaluate the kernel (default is 10)
The heat kernel
Kt (double (*,*,*))
Overload of replab.Str.hiddenFields
Tests if a graph is bipartite
true iff the graph is bipartite
ok (bool)
Returns the graph Laplacian
This is a generalized laplacian which also takes into account the graph coloring. It reduces to the standard laplacian when self.color = 0. A graph laplacian is semidefinite positive
Laplacian of the graph
L (double (*,*))
Returns the number of vertices at a distance 2 of vertex v
Returns the number of vertices at a distance 2 of all vertices
list of degrees
deg (double (1,*))
Example
>>> replab.UndirectedGraph.fromEdges([1 3]).secondOrderDegrees
1 0 1
Bases: replab.graph.Graph
Describes an immutable undirected graph
Class members list
Properties
colors
– color of each all vertices; if a scalar, identical for all vertices
edges
– list of edges between vertices
nVertices
– number of vertices in the graph
weights
– weights associated to the edges; if a scalar, identical for all edges
Prettyprinting
additionalFields
– Overload of replab.Str.additionalFields
disp
– Standard MATLAB/Octave display method
headerStr
– Header string representing the object
hiddenFields
– Overload of replab.Str.hiddenFields
longStr
– Multi-line description of the current object
shortStr
– Single line text description of the current object
Property cache
cache
– Sets the value of the designated property in the cache
cached
– Returns the cached property if it exists, computing it if necessary
cachedOrDefault
– Returns the cached property if it exists, or the provided default value if it is unknown yet
cachedOrEmpty
– Returns the cached property if it exists, or []
if it is unknown yet
inCache
– Returns whether the value of the given property has already been computed
Laws
check
– Checks the consistency of this object
checkAndContinue
– Checks the consistency of this object
laws
– Returns the laws that this object obeys
Unique ID
eq
– Equality test
id
– Returns the unique ID of this object (deprecated)
isequal
– Equality test
ne
– Non-equality test
General
UndirectedGraph
– Construct an undirected graph
Methods
adjacencyMatrix
– Returns the adjacency matrix of a graph
automorphismGroup
– Returns the automorphism group of the graph
computeAdjacencyMatrix
– Computes the adjacency matrix
computeHeatKernel
– Computes the heat kernel
computeLaplacian
– Computes the graph Laplacian
connectedComponents
– Returns the sets of vertices corresponding to connected components
degree
– Returns the degrees of vertex v
degrees
– Returns the degrees of all vertices
degreesSequence
– Returns the degrees sequence for all vertices
degreesSequences
– Returns the degrees sequence for all vertices
heatKernel
– The heat kernel
isBipartite
– Tests if a graph is bipartite
laplacian
– Returns the graph Laplacian
secondOrderDegree
– Returns the number of vertices at a distance 2 of all vertices
secondOrderDegrees
– Returns the number of vertices at a distance 2 of all vertices
toDirectedGraph
– Adds directionality to the graph’s edges
Constructors
fromAdjacencyMatrix
– Constructs an undirected graph from an adjacency matrix
fromBiadjacencyMatrix
– Constructs an undirected graph from a biadjacency matrix
fromDirectedGraph
– Define an undirected graph from a directed one
fromEdges
– Constructs a undirected graph from a liste of edges
fromFile
– Loads a graph from a Bliss file
Inherited elements
Documentation in replab.graph.Graph.additionalFields()
Documentation in replab.graph.Graph.adjacencyMatrix()
Documentation in replab.graph.Graph.automorphismGroup()
Documentation in replab.Obj.cache()
Documentation in replab.Obj.cached()
Documentation in replab.Obj.cachedOrDefault()
Documentation in replab.Obj.cachedOrEmpty()
Documentation in replab.Obj.check()
Documentation in replab.Obj.checkAndContinue()
Documentation in replab.graph.Graph.colors
Documentation in replab.graph.Graph.computeHeatKernel()
Documentation in replab.graph.Graph.connectedComponents()
Documentation in replab.graph.Graph.degreesSequence()
Documentation in replab.graph.Graph.degreesSequences()
Documentation in replab.Str.disp()
Documentation in replab.graph.Graph.edges
Documentation in replab.Obj.eq()
Documentation in replab.graph.Graph.heatKernel()
Documentation in replab.graph.Graph.hiddenFields()
Documentation in replab.Obj.id()
Documentation in replab.Obj.inCache()
Documentation in replab.graph.Graph.isBipartite()
Documentation in replab.Obj.isequal()
Documentation in replab.graph.Graph.laplacian()
Documentation in replab.Obj.laws()
Documentation in replab.Str.longStr()
Documentation in replab.graph.Graph.nVertices
Documentation in replab.Obj.ne()
Documentation in replab.graph.Graph.secondOrderDegrees()
Documentation in replab.Str.shortStr()
Documentation in replab.graph.Graph.weights
Construct an undirected graph
Do not use this function direclty, rather use another
constructor such as fromAdjacencyMatrix
.
Computes the adjacency matrix
Computes the graph Laplacian
Returns the degrees of vertex v
v (integer
) – vertex number
list of degrees
deg (double (1,*))
Example
>>> graph = replab.UndirectedGraph.fromEdges([1 3; 1 4]);
>>> graph.degree(1)
2
Returns the degrees of all vertices
list of degrees
deg (double (1,*))
Example
>>> replab.UndirectedGraph.fromEdges([1 3]).degrees
1 0 1
Constructs an undirected graph from an adjacency matrix
The element (i,j) of an adjacency matrix is 1 only if vertex i is connected to vertex j. Alternatively, the value of the matrix element is the weight associated to this edge.
adj (double (*,*)
) – the adjacency matrix
colors (double (*,1), optional
) – coloring of the vertices
graph (UndirectedGraph
)
Example
>>> replab.UndirectedGraph.fromAdjacencyMatrix([0 1 1; 1 0 1; 1 1 0])
Undirected graph with 3 vertices and 3 edges
edges: [1, 2; 1, 3; 2, 3]
Constructs an undirected graph from a biadjacency matrix
A bipartite undirected graph is one in which vertices can be divided into two sets, such that edges only connect vertices belonging to different sets.
The element (i,j) of an biadjacency matrix is 1 for an undirected bipartite graph iff vertex i of the first set of vertices is linked with vertex j in the second set of vertices. Alternatively, the value of the matrix element is the weight associated to this edge.
biadj (double (*,*)
) – array of vertices linked by an edge
colors (double (*,1), optional
) – coloring of the row vertices
colors – coloring of the column vertices
graph (UndirectedGraph
)
Example
>>> replab.UndirectedGraph.fromBiadjacencyMatrix([1 0 1; 1 1 0])
Undirected graph with 5 vertices and 4 edges
edges: [1, 3; 2, 3; 2, 4; 1, 5]
Define an undirected graph from a directed one
This function returns an undirected graph with the same connectivity as the input directed graph.
graph (DirectedGraph
) –
graph (UndirectedGraph
)
Constructs a undirected graph from a liste of edges
Duplicated edges are merged. Their weights are added up iff a weights was defined individually for each edge.
edges (integer (*,2)
) – array of vertices linked by an edge
nVertices (integer, optional
) – number of vertices
colors (double (*,1), optional
) – coloring of the vertices
weights (double (*,1), optional
) – weight associated to each edge
graph (UndirectedGraph
)
Example
>>> replab.UndirectedGraph.fromEdges([1 2; 2 3; 3 1], 3)
Undirected graph with 3 vertices and 3 edges
edges: [1, 2; 1, 3; 2, 3]
Loads a graph from a Bliss file
Following the specifications from http://www.tcs.hut.fi/Software/bliss/fileformat.shtml
fileName (charstring
) – Name of the file to be loaded
graph (UndirectedGraph
)
Header string representing the object
description of the object
charstring
Returns the number of vertices at a distance 2 of all vertices
v (integer
) – vertex number
list of degrees
deg (double (1,*))
Example
>>> graph = replab.UndirectedGraph.fromEdges([1 3]);
>>> graph.secondOrderDegree(1)
1
Adds directionality to the graph’s edges
This function returns an directed graph with the same connectivity as the current graph.
graph (DirectedGraph
)
Bases: replab.graph.Graph
Describes an immutable directed graphs
Class members list
Properties
colors
– color of each all vertices; if a scalar, identical for all vertices
edges
– list of edges between vertices
nVertices
– number of vertices in the graph
weights
– weights associated to the edges; if a scalar, identical for all edges
Prettyprinting
additionalFields
– Overload of replab.Str.additionalFields
disp
– Standard MATLAB/Octave display method
headerStr
– Header string representing the object
hiddenFields
– Overload of replab.Str.hiddenFields
longStr
– Multi-line description of the current object
shortStr
– Single line text description of the current object
Property cache
cache
– Sets the value of the designated property in the cache
cached
– Returns the cached property if it exists, computing it if necessary
cachedOrDefault
– Returns the cached property if it exists, or the provided default value if it is unknown yet
cachedOrEmpty
– Returns the cached property if it exists, or []
if it is unknown yet
inCache
– Returns whether the value of the given property has already been computed
Laws
check
– Checks the consistency of this object
checkAndContinue
– Checks the consistency of this object
laws
– Returns the laws that this object obeys
Unique ID
eq
– Equality test
id
– Returns the unique ID of this object (deprecated)
isequal
– Equality test
ne
– Non-equality test
Methods
adjacencyMatrix
– Returns the adjacency matrix of a graph
automorphismGroup
– Returns the automorphism group of the graph
computeAdjacencyMatrix
– Computes the adjacency matrix
computeHeatKernel
– Computes the heat kernel
computeLaplacian
– Computes the graph Laplacian
connectedComponents
– Returns the sets of vertices corresponding to connected components
degree
– Returns the degrees of vertex v
degrees
– Returns the degrees of all vertices
degreesSequence
– Returns the degrees sequence for all vertices
degreesSequences
– Returns the degrees sequence for all vertices
heatKernel
– The heat kernel
isBipartite
– Tests if a graph is bipartite
laplacian
– Returns the graph Laplacian
secondOrderDegree
– Returns the number of vertices at a distance 2 of all vertices
secondOrderDegrees
– Returns the number of vertices at a distance 2 of all vertices
toUndirectedGraph
– Removes the graph directionality
Constructors
fromAdjacencyMatrix
– Constructs a directed graph from an adjacency matrix
fromBiadjacencyMatrix
– Constructs a directed graph from a biadjacency matrix
fromEdges
– Constructs a directed graph from a liste of edges
fromFile
– Loads a graph from a Bliss file
fromUndirectedGraph
– Define an directed graph from an undirected one
Inherited elements
Documentation in replab.graph.Graph.additionalFields()
Documentation in replab.graph.Graph.adjacencyMatrix()
Documentation in replab.graph.Graph.automorphismGroup()
Documentation in replab.Obj.cache()
Documentation in replab.Obj.cached()
Documentation in replab.Obj.cachedOrDefault()
Documentation in replab.Obj.cachedOrEmpty()
Documentation in replab.Obj.check()
Documentation in replab.Obj.checkAndContinue()
Documentation in replab.graph.Graph.colors
Documentation in replab.graph.Graph.computeHeatKernel()
Documentation in replab.graph.Graph.connectedComponents()
Documentation in replab.graph.Graph.degreesSequence()
Documentation in replab.graph.Graph.degreesSequences()
Documentation in replab.Str.disp()
Documentation in replab.graph.Graph.edges
Documentation in replab.Obj.eq()
Documentation in replab.graph.Graph.heatKernel()
Documentation in replab.graph.Graph.hiddenFields()
Documentation in replab.Obj.id()
Documentation in replab.Obj.inCache()
Documentation in replab.graph.Graph.isBipartite()
Documentation in replab.Obj.isequal()
Documentation in replab.graph.Graph.laplacian()
Documentation in replab.Obj.laws()
Documentation in replab.Str.longStr()
Documentation in replab.graph.Graph.nVertices
Documentation in replab.Obj.ne()
Documentation in replab.graph.Graph.secondOrderDegrees()
Documentation in replab.Str.shortStr()
Documentation in replab.graph.Graph.weights
Computes the adjacency matrix
Computes the graph Laplacian
The laplacian should be positive semi-definite, so we define it from the equivalent un-directed graph
Returns the degrees of vertex v
v (integer
) – vertex number
list of degrees
deg (double (1,*))
Example
>>> graph = replab.DirectedGraph.fromEdges([1 3; 1 4]);
>>> graph.degree(1)
2
Returns the degrees of all vertices
list of degrees
deg (double (1,*))
Example
>>> replab.DirectedGraph.fromEdges([1 3]).degrees
1 0 1
Constructs a directed graph from an adjacency matrix
The element (i,j) of an adjacency matrix is 1 iff vertex i is linked to vertex j. Alternatively, the value of the matrix element is the weight associated to this edge.
adj (double (*,*)
) – the adjacency matrix
colors (double (*,1), optional
) – coloring of the vertices
graph (DirectedGraph
)
Example
>>> replab.DirectedGraph.fromAdjacencyMatrix([0 1 1; 1 0 1; 1 1 0])
Directed graph with 3 vertices and 6 edges
edges: [2, 1; 3, 1; 1, 2; 3, 2; 1, 3; 2, 3]
Constructs a directed graph from a biadjacency matrix
A bipartite directed graph is one in which vertices can be divided into two sets, such that edges only connect vertices belonging to different sets. Moreover all edges are directed from the first set to the second one.
The element (i,j) of an biadjacency matrix is 1 for an directed bipartite graph iff vertex i of the first set of verices is linked to vertex j in the second set of vertices. Alternatively, the value of the matrix element is the weight associated to this edge.
biadj (double (*,*)
) – array of vertices linked by an edge
graph (DirectedGraph
)
Example
>>> replab.DirectedGraph.fromBiadjacencyMatrix([1 0 1; 1 1 0])
Directed graph with 5 vertices and 4 edges
edges: [1, 3; 2, 3; 2, 4; 1, 5]
Constructs a directed graph from a liste of edges
Duplicated edges are merged. Their weights are added up iff a weight was defined individually for each edge.
edges (integer (*,2)
) – array of vertices linked by an edge
nVertices (integer, optional
) – number of vertices
colors (double (*,1), optional
) – coloring of the vertices
weights (double (*,1), optional
) – weight associated to each edge
graph (DirectedGraph
)
Example
>>> replab.DirectedGraph.fromEdges([1 2; 2 3; 3 1], 3)
Directed graph with 3 vertices and 3 edges
edges: [1, 2; 2, 3; 3, 1]
Loads a graph from a Bliss file
Following the specifications from http://www.tcs.hut.fi/Software/bliss/fileformat.shtml
fileName (charstring
) – Name of the file to be loaded
graph (UndirectedGraph
)
Define an directed graph from an undirected one
This function returns an directed graph with the same connectivity as the input undirected graph.
graph (UndirectedGraph
) –
graph (DirectedGraph
)
Header string representing the object
description of the object
charstring
Returns the number of vertices at a distance 2 of all vertices
v (integer
) – vertex number
list of degrees
deg (double (1,*))
Example
>>> replab.DirectedGraph.fromEdges([1 3]).secondOrderDegrees
1 0 1
Removes the graph directionality
This function returns an undirected graph with the same connectivity as the current graph.
graph (DirectedGraph
)