Graph

Graph Class

class kedgeswap.Graph.Graph(directed=False)

Bases: object

Read input graph and store graph as adjacency list

N

number of nodes

Type:

int

M

number of edges

Type:

int

neighbors

store adjacency list for each node

Type:

dict(list)

in_neighbors

used only in directed graph, for each node store their neighbors from “in-edges”

Type:

dict(list)

out_neighbors

used only in directed graph, for each node store their neighbors from “out-edges”

Type:

dict(list)

edges

in undirected graph:

* for each edge (u,v), store the position | of v in the adjacency list of u | in directed graph:

* for each edge (u,v), store a quartuplet | (v_idx, u_idx, v_out_idx, u_in_idx), where: | v_idx is the position of v in u’s adjacency list | u_idx is the position of u in v’s adjacency list | v_out_idx is the position of v in out_neighbors[u]_ | u_in_idx is the position of u in in_neighbors[v] unique_edges: list()

used mostly for undirected graph, to store one version of each edge

Type:

dict()

directed

enable if graph is directed

Type:

bool

copy()

read_ssv(in_file)

Read space separated values Input format is separated with spaces or tabulations, e.g.:

0 1

3 2

2 4

.

.

.

where the first columns is the source node and the second column is the destination node. |When self.directed == True, the graph is considered directed and edges are stored as written in the file, else they are stored as (src, dest) with src < dest. Self Loop and multi-graphs are not accepted.

Parameters:

in_file (str) – path to the input file

read_ael(in_file)

Read ael format TODO example format TODO lecteurs pour d’autres formats

to_ael(output)

to_ssv(output)