Graph
Graph Class
- class kedgeswap.Graph.Graph(directed=False)[source]
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
- read_ssv(in_file)[source]
Read space separated values Input format is separated with spaces or tabulations, e.g.:
0 13 22 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