1. API
  2. Graphs

Graphs

graph.Graph

class replab.graph.Graph(nVertices, edges, colors, weights)

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

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

Constructors

Inherited elements

cache(self, name, value, handleExisting)

Documentation in replab.Obj.cache()

cached(self, name, fun)

Documentation in replab.Obj.cached()

cachedOrDefault(self, name, defaultValue)

Documentation in replab.Obj.cachedOrDefault()

cachedOrEmpty(self, name)

Documentation in replab.Obj.cachedOrEmpty()

check(self)

Documentation in replab.Obj.check()

checkAndContinue(self)

Documentation in replab.Obj.checkAndContinue()

disp(self)

Documentation in replab.Str.disp()

eq(self, rhs)

Documentation in replab.Obj.eq()

headerStr(self)

Documentation in replab.Str.headerStr()

id(self)

Documentation in replab.Obj.id()

inCache(self, name)

Documentation in replab.Obj.inCache()

isequal(lhs, rhs)

Documentation in replab.Obj.isequal()

laws(self)

Documentation in replab.Obj.laws()

longStr(self, maxRows, maxColumns)

Documentation in replab.Str.longStr()

ne(self, rhs)

Documentation in replab.Obj.ne()

shortStr(self, maxColumns)

Documentation in replab.Str.shortStr()

Own members

colors

color of each all vertices; if a scalar, identical for all vertices

Type

double (*,1)

edges

list of edges between vertices

Type

integer (*,2)

nVertices

number of vertices in the graph

Type

integer

weights

weights associated to the edges; if a scalar, identical for all edges

Type

double (*,1)

additionalFields(self)

Overload of replab.Str.additionalFields

adjacencyMatrix(self)

Returns the adjacency matrix of a graph

Returns

adjacency matrix

Return type

adj (double (*,*))

Example

>>> replab.UndirectedGraph.fromEdges([1 3]).adjacencyMatrix
  0     0     1
  0     0     0
  1     0     0
automorphismGroup(self)

Returns the automorphism group of the graph

Returns

autoG (replab.PermutationGroup)

computeAdjacencyMatrix(self)

Computes the adjacency matrix

computeHeatKernel(self, nbTimes)

Computes the heat kernel

computeLaplacian(self)

Computes the graph Laplacian

connectedComponents(self)

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.

Returns

Partitioning of the vertices

Return type

P (replab.Partition)

Example

>>> replab.UndirectedGraph.fromEdges([1 3]).connectedComponents
  Partition '13|2'
  blockIndex: [1, 2, 1]
      blocks: {[1, 3], 2}
           n: 3
degree(self, v)

Returns the degrees of vertex v

degrees(self)

Returns the degrees of all vertices

degreesSequence(self, v)

Returns the degrees sequence for all vertices

Each vertex can only be counted once. For directed graphs, this corresponds to the outgoing degree sequence.

Returns

sequence of degrees

Return type

degN (integer (1,*))

Example

>>> graph = replab.DirectedGraph.fromEdges([1 3]);
>>> graph.degreesSequence(1)
  1
degreesSequences(self)

Returns the degrees sequence for all vertices

In each sequence, a vertex can only be counted once.

Returns

list of degrees sequences

Return type

degN (integer (*,*))

Example

>>> replab.UndirectedGraph.fromEdges([1 3]).degreesSequences
  1
  0
  1
static fromAdjacencyMatrix(adj, colors)

Constructs a directed graph from an adjacency matrix

static fromBiadjacencyMatrix(biadj)

Constructs a directed graph from a biadjacency matrix

static fromEdges(edges, nVertices, colors, weights)

Constructs a directed graph from a liste of edges

static fromFile(fileName)

Loads a graph from a Bliss file

heatKernel(self, nbTimes)

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.

Parameters

nbTimes (integer, optional) – the number of distinct times at which to evaluate the kernel (default is 10)

Returns

The heat kernel

Return type

Kt (double (*,*,*))

hiddenFields(self)

Overload of replab.Str.hiddenFields

isBipartite(self)

Tests if a graph is bipartite

Returns

true iff the graph is bipartite

Return type

ok (bool)

laplacian(self)

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

Returns

Laplacian of the graph

Return type

L (double (*,*))

secondOrderDegree(self, v)

Returns the number of vertices at a distance 2 of vertex v

secondOrderDegrees(self)

Returns the number of vertices at a distance 2 of all vertices

Returns

list of degrees

Return type

deg (double (1,*))

Example

>>> replab.UndirectedGraph.fromEdges([1 3]).secondOrderDegrees
  1     0     1

UndirectedGraph

class replab.UndirectedGraph(nVertices, edges, colors, weights)

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

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

Methods

Constructors

Inherited elements

additionalFields(self)

Documentation in replab.graph.Graph.additionalFields()

adjacencyMatrix(self)

Documentation in replab.graph.Graph.adjacencyMatrix()

automorphismGroup(self)

Documentation in replab.graph.Graph.automorphismGroup()

cache(self, name, value, handleExisting)

Documentation in replab.Obj.cache()

cached(self, name, fun)

Documentation in replab.Obj.cached()

cachedOrDefault(self, name, defaultValue)

Documentation in replab.Obj.cachedOrDefault()

cachedOrEmpty(self, name)

Documentation in replab.Obj.cachedOrEmpty()

check(self)

Documentation in replab.Obj.check()

checkAndContinue(self)

Documentation in replab.Obj.checkAndContinue()

colors

Documentation in replab.graph.Graph.colors

computeHeatKernel(self, nbTimes)

Documentation in replab.graph.Graph.computeHeatKernel()

connectedComponents(self)

Documentation in replab.graph.Graph.connectedComponents()

degreesSequence(self, v)

Documentation in replab.graph.Graph.degreesSequence()

degreesSequences(self)

Documentation in replab.graph.Graph.degreesSequences()

disp(self)

Documentation in replab.Str.disp()

edges

Documentation in replab.graph.Graph.edges

eq(self, rhs)

Documentation in replab.Obj.eq()

heatKernel(self, nbTimes)

Documentation in replab.graph.Graph.heatKernel()

hiddenFields(self)

Documentation in replab.graph.Graph.hiddenFields()

id(self)

Documentation in replab.Obj.id()

inCache(self, name)

Documentation in replab.Obj.inCache()

isBipartite(self)

Documentation in replab.graph.Graph.isBipartite()

isequal(lhs, rhs)

Documentation in replab.Obj.isequal()

laplacian(self)

Documentation in replab.graph.Graph.laplacian()

laws(self)

Documentation in replab.Obj.laws()

longStr(self, maxRows, maxColumns)

Documentation in replab.Str.longStr()

nVertices

Documentation in replab.graph.Graph.nVertices

ne(self, rhs)

Documentation in replab.Obj.ne()

secondOrderDegrees(self)

Documentation in replab.graph.Graph.secondOrderDegrees()

shortStr(self, maxColumns)

Documentation in replab.Str.shortStr()

weights

Documentation in replab.graph.Graph.weights

Own members

UndirectedGraph(nVertices, edges, colors, weights)

Construct an undirected graph

Do not use this function direclty, rather use another constructor such as fromAdjacencyMatrix .

computeAdjacencyMatrix(self)

Computes the adjacency matrix

computeLaplacian(self)

Computes the graph Laplacian

degree(self, v)

Returns the degrees of vertex v

Parameters

v (integer) – vertex number

Returns

list of degrees

Return type

deg (double (1,*))

Example

>>> graph = replab.UndirectedGraph.fromEdges([1 3; 1 4]);
>>> graph.degree(1)
  2
degrees(self)

Returns the degrees of all vertices

Returns

list of degrees

Return type

deg (double (1,*))

Example

>>> replab.UndirectedGraph.fromEdges([1 3]).degrees
  1     0     1
static fromAdjacencyMatrix(adj, colors)

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.

Parameters

  • adj (double (*,*)) – the adjacency matrix

  • colors (double (*,1), optional) – coloring of the vertices

Returns

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]
static fromBiadjacencyMatrix(biadj, colorsRows, colorsCols)

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.

Parameters

  • biadj (double (*,*)) – array of vertices linked by an edge

  • colors (double (*,1), optional) – coloring of the row vertices

  • colors – coloring of the column vertices

Returns

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]
static fromDirectedGraph(graph)

Define an undirected graph from a directed one

This function returns an undirected graph with the same connectivity as the input directed graph.

Parameters

graph (DirectedGraph) –

Returns

graph (UndirectedGraph)

static fromEdges(edges, nVertices, colors, weights)

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.

Parameters

  • 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

Returns

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]
static fromFile(fileName)

Loads a graph from a Bliss file

Following the specifications from http://www.tcs.hut.fi/Software/bliss/fileformat.shtml

Parameters

fileName (charstring) – Name of the file to be loaded

Returns

graph (UndirectedGraph)

headerStr(self)

Header string representing the object

Returns

description of the object

Return type

charstring

secondOrderDegree(self, v)

Returns the number of vertices at a distance 2 of all vertices

Parameters

v (integer) – vertex number

Returns

list of degrees

Return type

deg (double (1,*))

Example

>>> graph = replab.UndirectedGraph.fromEdges([1 3]);
>>> graph.secondOrderDegree(1)
  1
toDirectedGraph(self)

Adds directionality to the graph’s edges

This function returns an directed graph with the same connectivity as the current graph.

Returns

graph (DirectedGraph)

DirectedGraph

class replab.DirectedGraph(nVertices, edges, colors, weights)

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

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

Constructors

Inherited elements

additionalFields(self)

Documentation in replab.graph.Graph.additionalFields()

adjacencyMatrix(self)

Documentation in replab.graph.Graph.adjacencyMatrix()

automorphismGroup(self)

Documentation in replab.graph.Graph.automorphismGroup()

cache(self, name, value, handleExisting)

Documentation in replab.Obj.cache()

cached(self, name, fun)

Documentation in replab.Obj.cached()

cachedOrDefault(self, name, defaultValue)

Documentation in replab.Obj.cachedOrDefault()

cachedOrEmpty(self, name)

Documentation in replab.Obj.cachedOrEmpty()

check(self)

Documentation in replab.Obj.check()

checkAndContinue(self)

Documentation in replab.Obj.checkAndContinue()

colors

Documentation in replab.graph.Graph.colors

computeHeatKernel(self, nbTimes)

Documentation in replab.graph.Graph.computeHeatKernel()

connectedComponents(self)

Documentation in replab.graph.Graph.connectedComponents()

degreesSequence(self, v)

Documentation in replab.graph.Graph.degreesSequence()

degreesSequences(self)

Documentation in replab.graph.Graph.degreesSequences()

disp(self)

Documentation in replab.Str.disp()

edges

Documentation in replab.graph.Graph.edges

eq(self, rhs)

Documentation in replab.Obj.eq()

heatKernel(self, nbTimes)

Documentation in replab.graph.Graph.heatKernel()

hiddenFields(self)

Documentation in replab.graph.Graph.hiddenFields()

id(self)

Documentation in replab.Obj.id()

inCache(self, name)

Documentation in replab.Obj.inCache()

isBipartite(self)

Documentation in replab.graph.Graph.isBipartite()

isequal(lhs, rhs)

Documentation in replab.Obj.isequal()

laplacian(self)

Documentation in replab.graph.Graph.laplacian()

laws(self)

Documentation in replab.Obj.laws()

longStr(self, maxRows, maxColumns)

Documentation in replab.Str.longStr()

nVertices

Documentation in replab.graph.Graph.nVertices

ne(self, rhs)

Documentation in replab.Obj.ne()

secondOrderDegrees(self)

Documentation in replab.graph.Graph.secondOrderDegrees()

shortStr(self, maxColumns)

Documentation in replab.Str.shortStr()

weights

Documentation in replab.graph.Graph.weights

Own members

computeAdjacencyMatrix(self)

Computes the adjacency matrix

computeLaplacian(self)

Computes the graph Laplacian

The laplacian should be positive semi-definite, so we define it from the equivalent un-directed graph

degree(self, v)

Returns the degrees of vertex v

Parameters

v (integer) – vertex number

Returns

list of degrees

Return type

deg (double (1,*))

Example

>>> graph = replab.DirectedGraph.fromEdges([1 3; 1 4]);
>>> graph.degree(1)
  2
degrees(self)

Returns the degrees of all vertices

Returns

list of degrees

Return type

deg (double (1,*))

Example

>>> replab.DirectedGraph.fromEdges([1 3]).degrees
  1     0     1
static fromAdjacencyMatrix(adj, colors)

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.

Parameters

  • adj (double (*,*)) – the adjacency matrix

  • colors (double (*,1), optional) – coloring of the vertices

Returns

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]
static fromBiadjacencyMatrix(biadj)

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.

Parameters

biadj (double (*,*)) – array of vertices linked by an edge

Returns

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]
static fromEdges(edges, nVertices, colors, weights)

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.

Parameters

  • 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

Returns

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]
static fromFile(fileName)

Loads a graph from a Bliss file

Following the specifications from http://www.tcs.hut.fi/Software/bliss/fileformat.shtml

Parameters

fileName (charstring) – Name of the file to be loaded

Returns

graph (UndirectedGraph)

static fromUndirectedGraph(graph)

Define an directed graph from an undirected one

This function returns an directed graph with the same connectivity as the input undirected graph.

Parameters

graph (UndirectedGraph) –

Returns

graph (DirectedGraph)

headerStr(self)

Header string representing the object

Returns

description of the object

Return type

charstring

secondOrderDegree(self, v)

Returns the number of vertices at a distance 2 of all vertices

Parameters

v (integer) – vertex number

Returns

list of degrees

Return type

deg (double (1,*))

Example

>>> replab.DirectedGraph.fromEdges([1 3]).secondOrderDegrees
  1     0     1
toUndirectedGraph(self)

Removes the graph directionality

This function returns an undirected graph with the same connectivity as the current graph.

Returns

graph (DirectedGraph)

© Copyright 2018-2022, Denis Rosset, Jean-Daniel Bancal and collaborators. Created using Sphinx.