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]
- 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.
- dfs_traversal(root: Any) List[Any] [source]
Compute a depth 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)))
- 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.