Lib.Graphes module

Python Classes for Oriented and Non Oriented Graphs

exception Lib.Graphes.GraphError(message: str)[source]

Bases: Exception

Exception raised for self loops.

message: str
class Lib.Graphes.GeneralGraph(graph_dict=None)[source]

Bases: object

General class regrouping similarities between directed and non oriented graphs. The only differences between the two are:

  • how to compute the set of edges

  • how to add an edge

  • how to print the graph

  • how to delete a vertex

  • how to delete an edge

  • we only color undirected graphs

graph_dict: Dict[Any, Set]
vertices() List[Any][source]

Return the vertices of a graph.

add_vertex(vertex: Any) None[source]

If the vertex “vertex” is not in self.graph_dict, a key “vertex” with an empty list as a value is added to the dictionary. Otherwise nothing has to be done.

edges() List[Set][source]

Return the edges of the graph.

dfs_traversal(root: Any) List[Any][source]

Compute a depth first search of the graph, from the vertex root.

is_reachable_from(v1: Any, v2: Any) bool[source]

True if there is a path from v1 to v2.

connected_components() List[List[Any]][source]

Compute the list of all connected components of the graph, each component being a list of vetices.

bfs_traversal(root: Any) List[Any][source]

Compute a breadth first search of the graph, from the vertex root.

class Lib.Graphes.Graph(graph_dict=None)[source]

Bases: GeneralGraph

Class for non oriented graphs.

edges() List[Set][source]

A static method generating the set of edges (they appear twice in the dictionnary). Return a list of sets.

add_edge(edge: Tuple[Any, Any]) None[source]

Add an edge in the graph. edge should be a pair and not (c,c) (we call g.add_edge((v1,v2)))

print_dot(name: str, colors={}) None[source]

Print the graph.

delete_vertex(vertex: Any) None[source]

Delete a vertex and all the adjacent edges.

delete_edge(edge: Tuple[Any, Any])[source]

Delete an edge.

color() Dict[Any, int][source]

Color the graph with an unlimited number of colors. Return a dict vertex -> color, where color is an integer (0, 1, …).

color_with_k_colors(K=None, avoidingnodes=()) Tuple[Dict[Any, int], bool, List][source]

Color with <= K colors (if K is unspecified, use unlimited colors).

Return 3 values:

  • a dict vertex -> color

  • a Boolean, True if the coloring succeeded

  • the set of nodes actually colored

Do not color vertices belonging to avoidingnodes.

Continue even if the algo fails.

class Lib.Graphes.DiGraph(graph_dict=None)[source]

Bases: GeneralGraph

Class for directed graphs.

pred(v: Any) Set[source]

Return all predecessors of the vertex v in the graph.

neighbourhoods() List[Tuple[Any, Set]][source]

Return all neighbourhoods in the graph.

edges() List[Tuple[Any, Any]][source]

A static method generating the set of edges

add_edge(edge: Tuple[Any, Any]) None[source]

Add an edge in the graph. edge should be a pair and not (c,c) (we call g.add_edge((v1,v2)))

print_dot(name: str) None[source]

Print the graph.

delete_vertex(vertex: Any) None[source]

Delete a vertex and all the adjacent edges.

delete_edge(edge: Tuple[Any, Any]) None[source]

Delete an edge.