ChordlessPath module¶
-
ChordlessPath.bfs_path(G, source, destination)¶ Use a breadth first search to find the path from vertex source to vertex destination.
- Parameters
- Gnx.Graph
The graph to search
- sourcePoint
Origin point
- destinationPoint
Destination point
- Returns
- deque
A queue with the path from source to destination already enqueued.
-
ChordlessPath.chordless_path(G, t, Q, P, master_Q)¶ Find all the chordless paths from source to target.
Q and P are recursive helper variables.
- Parameters
- Gnx.Graph
The Graph to find the chordless paths in
- tPoint
The target point for the path
- QList
A list of the current path from the original source to target
- Pdeque
A SimpleQueue representing the breadth first search path from source to target
- master_QList of List
A List of List such that each list in the list is a chordless path
- Returns
- List
The list of vertices from the original source to the target vertex
-
ChordlessPath.comp_rep(comp_ptr, u)¶ Find the component representative for the input vertex
- Parameters
- comp_ptrDict
The dictionary of component pointers
- uPoint
The vertex of interest
- Returns
- Point :
The component representative of the component u is a part of
-
ChordlessPath.components(G)¶ Find the components of graph G
- Parameters
- Gnx.Graph
The graph to find the connected components in
- Returns
- Dict of Point
A dictionary such that each Point in the dictionary points to it’s component representative or the size of the component that it represents
-
ChordlessPath.merge(comp_ptr, u_rep, v_rep)¶ Merge the smaller component into the larger one
- Parameters
- comp_ptrDict of Point
The list of component pointers
- u_repPoint
The component representative for the first component
- v_repPoint
The component representative for the first component
-
ChordlessPath.remove_edge(G, u, v)¶ Remove the edge u``v from graph G
- Parameters
- Gnx.Graph
The graph from which the edge will be removed
- uPoint
The first endpoint of the edge
- vPoint
The second endpoint of the edge
- Returns
- nx.Graph
A copy of the graph G without the u``v edge
-
ChordlessPath.remove_vertices(G, vertices)¶ Remove all vertices in vertices from the graph G
- Parameters
- Gnx.Graph
The graph from which vertices will be removed
- verticeslist
The list of vertices in G to be removed
- Returns
- nx.Graph
A copy of the graph G without the vertices listed in vertices