# 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

### 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)

Overload of `replab.Str.additionalFields`

Returns the adjacency matrix of a graph

Returns

Return type

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

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

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
```

Constructs a directed graph from an adjacency matrix

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

### Own members

UndirectedGraph(nVertices, edges, colors, weights)

Construct an undirected graph

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

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
```

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]
```

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`)

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

### Own members

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
```

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]
```

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`)

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`)