# itu.algs4.graphs package¶

## itu.algs4.graphs.acyclic_lp module¶

class `itu.algs4.graphs.acyclic_lp.``AcyclicLp`(edge_weighted_digraph, s)

Bases: `object`

The AcyclicLP class represents a data type for solving the single-source longest paths problem in edge-weighted directed acyclic graphs (DAGs). The edge weights can be positive, negative, or zero.

This implementation uses a topological-sort based algorithm. The constructor takes time proportional to V + E, where V is the number of vertices and E is the number of edges. Each call to distTo(int) and hasPathTo(int) takes constant time; each call to pathTo(int) takes time proportional to the number of edges in the shortest path returned.

For additional documentation, see Section 4.4 of Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.

`dist_to`(v)

Returns the length of a longest path from the source vertex s to vertex v.

Parameters: v – the destination vertex the length of a longest path from the source vertex s to vertex v; negative infinity if no such path exists
`has_path_to`(v)

Is there a path from the source vertex s to vertex v?

`path_to`(v)

Returns a longest path from the source vertex s to vertex v.

Param: the destination vertex a longest path from the source vertex s to vertex v as an iterable of edges, and None if no such path

## itu.algs4.graphs.acyclic_sp module¶

class `itu.algs4.graphs.acyclic_sp.``AcyclicSP`(G, s)

Bases: `object`

The AcyclicSP class represents a data type for solving the single-source shortest paths problem in edge-weighted directed acyclic graphs (DAGs). The edge weights can be positive, negative, or zero.

This implementation uses a topological-sort based algorithm. The constructor takes time proportional to V + E, where V is the number of vertices and E is the number of edges. Each call to distTo(int) and has_path_to(int) takes constant time each call to pathTo(int) takes time proportional to the number of edges in the shortest path returned.

`dist_to`(v)

Returns the length of a shortest path from the source vertex s to vertex v.

Parameters: v – the destination vertex the length of a shortest path from the source vertex s to vertex v math.inf if no such path ValueError – unless 0 <= v < V
`has_path_to`(v)

Is there a path from the source vertex s to vertex v?

Parameters: v – the destination vertex true if there is a path from the source vertex s to vertex v, and false otherwise ValueError – unless 0 <= v < V
`path_to`(v)

Returns a shortest path from the source vertex s to vertex v.

Parameters: v – the destination vertex a shortest path from the source vertex s to vertex v as an iterable of edges, and None if no such path ValueError – unless 0 <= v < V

## itu.algs4.graphs.bellman_ford_sp module¶

class `itu.algs4.graphs.bellman_ford_sp.``BellmanFordSP`(G, s)

Bases: `object`

`dist_to`(v)
`has_negative_cycle`()
`has_path_to`(v)
`negative_cycle`()
`path_to`(v)
`itu.algs4.graphs.bellman_ford_sp.``main`(args)

## itu.algs4.graphs.bipartite module¶

class `itu.algs4.graphs.bipartite.``Bipartite`(G)

Bases: `object`

The Bipartite class represents a data type for determining whether an undirected graph is bipartite or whether it has an odd-length cycle. The isBipartite operation determines whether the graph is bipartite. If so, the color operation determines a bipartition if not, the oddCycle operation determines a cycle with an odd number of edges.

This implementation uses depth-first search. The constructor takes time proportional to V + E (in the worst case), where V is the number of vertices and E is the number of edges. Afterwards, the isBipartite and color operations take constant time the oddCycle operation takes time proportional to the length of the cycle. See BipartiteX for a nonrecursive version that uses breadth-first search.

exception `UnsupportedOperationException`

Bases: `Exception`

`color`(v)

Returns the side of the bipartite that vertex v is on.

Parameters: v – the vertex the side of the bipartition that vertex v is on two vertices are in the same side of the bipartition if and only if they have the same color IllegalArgumentException – unless 0 <= v < V UnsupportedOperationException – if this method is called when the graph is not bipartite
`is_bipartite`()

Returns True if the graph is bipartite.

Returns: True if the graph is bipartite False otherwise
`odd_cycle`()

Returns an odd-length cycle if the graph is not bipartite, and None otherwise.

Returns: an odd-length cycle if the graph is not bipartite (and hence has an odd-length cycle), and None otherwise

class `itu.algs4.graphs.breadth_first_paths.``BreadthFirstPaths`(G, s)

Bases: `object`

The BreadthFirstPaths class represents a data type for finding shortest paths (number of edges) from a source vertex s (or a set of source vertices) to every other vertex in a directed or undirected graph.

This implementation uses breadth-first search. The constructor takes time proportional to V + E, where V is the number of vertices and E is the number of edges. Each call to distTo(int) and hasPathTo(int) takes constant time each call to pathTo(int) takes time proportional to the length of the path. It uses extra space (not including the graph) proportional to V.

`dist_to`(v)

Returns the number of edges in a shortest path between the source vertex s (or sources) and vertex v?

Parameters: v – the vertex the number of edges in a shortest path ValueError – unless 0 <= v < V
`has_path_to`(v)

Is there a path between the source vertex s (or sources) and vertex v?

Parameters: v – the vertex true if there is a path, and False otherwise ValueError – unless 0 <= v < V
`path_to`(v)

Returns a shortest path between the source vertex s (or sources) and v, or null if no such path.

Parameters: v – the vertex the sequence of vertices on a shortest path, as an Iterable ValueError – unless 0 <= v < V
class `itu.algs4.graphs.breadth_first_paths.``BreadthFirstPathsBook`(G, s)

Bases: `object`

`has_path_to`(v)
`path_to`(v)

## itu.algs4.graphs.cc module¶

class `itu.algs4.graphs.cc.``CC`(G)

Bases: `object`

The CC class represents a data type for determining the connected components in an undirected graph. The id operation determines in which connected component a given vertex lies the connected operation determines whether two vertices are in the same connected component the count operation determines the number of connected components and the size operation determines the number of vertices in the connect component containing a given vertex.

The component identifier of a connected component is one of the vertices in the connected component: two vertices have the same component identifier if and only if they are in the same connected component.

This implementation uses depth-first search. The constructor takes time proportional to V + E (in the worst case), where V is the number of vertices and E is the number of edges. Afterwards, the id, count, connected, and size operations take constant time.

`connected`(v, w)

Returns true if vertices v and w are in the same connected component.

Parameters: v – one vertex w – the other vertex True if vertices v and w are in the same connected component; False otherwise ValueError – unless 0 <= v < V ValueError – unless 0 <= w < V
`count`()

Returns the number of connected components in the graph G.

Returns: the number of connected components in the graph G
`id`(v)

Returns the component id of the connected component containing vertex v.

Parameters: v – the vertex the component id of the connected component containing vertex v ValueError – unless 0 <= v < V
`size`(v)

Returns the number of vertices in the connected component containing vertex v.

Parameters: v – the vertex the number of vertices in the connected component containing vertex v ValueError – unless 0 <= v < V
class `itu.algs4.graphs.cc.``CCBook`(G)

Bases: `object`

`connected`(v, w)
`count`()
`id`(v)

## itu.algs4.graphs.cycle module¶

class `itu.algs4.graphs.cycle.``Cycle`(G)

Bases: `object`

The Cycle class represents a data type for determining whether an undirected graph has a cycle. The hasCycle operation determines whether the graph has a cycle and, if so, the cycle operation returns one.

This implementation uses depth-first search. The constructor takes time proportional to V + E (in the worst case), where V is the number of vertices and E is the number of edges. Afterwards, the hasCycle operation takes constant time the cycle operation takes time proportional to the length of the cycle.

`cycle`()

Returns a cycle in the graph G.

Returns: a cycle if the graph G has a cycle, and null otherwise
`has_cycle`()

Returns true if the graph G has a cycle.

Returns: true if the graph has a cycle false otherwise

## itu.algs4.graphs.degrees_of_separation module¶

class `itu.algs4.graphs.degrees_of_separation.``DegreesOfSeparation`

Bases: `object`

The DegreesOfSeparation class provides a client for finding the degree of separation between one distinguished individual and every other individual in a social network. As an example, if the social network consists of actors in which two actors are connected by a link if they appeared in the same movie, and Kevin Bacon is the distinguished individual, then the client computes the Kevin Bacon number of every actor in the network.

The running time is proportional to the number of individuals and connections in the network. If the connections are given implicitly, as in the movie network example (where every two actors are connected if they appear in the same movie), the efficiency of the algorithm is improved by allowing both movie and actor vertices and connecting each movie to all of the actors that appear in that movie.

static `main`(args)

Reads in a social network from a file, and then repeatedly reads in individuals from standard input and prints out their degrees of separation. Takes three command-line arguments: the name of a file, a delimiter, and the name of the distinguished individual. Each line in the file contains the name of a vertex, followed by a list of the names of the vertices adjacent to that vertex, separated by the delimiter.

Parameters: args – the command-line arguments

## itu.algs4.graphs.depth_first_order module¶

class `itu.algs4.graphs.depth_first_order.``DepthFirstOrder`(digraph)

Bases: `object`

The DepthFirstOrder class represents a data type for determining depth- first search ordering of the vertices in a digraph or edge-weighted digraph, including preorder, postorder, and reverse postorder.

This implementation uses depth-first search. The constructor takes time proportional to V + E (in the worst case), where V is the number of vertices and E is the number of edges. Afterwards, the preorder, postorder, and reverse postorder operation takes take time proportional to V.

For additional documentation, see Section 4.2 of Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.

`post`(v=None)

Either returns the postorder number of vertex v or, if v is None, returns the vertices in postorder.

Parameters: v – None, or the vertex to return the postorder number of if v is None, the vertices in postorder, otherwise the postorder

number of v

`pre`(v=None)

Either returns the preorder number of vertex v or, if v is None, returns the vertices in preorder.

Parameters: v – None, or the vertex to return the preorder number of if v is None, the vertices in preorder, otherwise the preorder number of v
`reverse_post`()

Returns the vertices in reverse postorder.

Returns: the vertices in reverse postorder, as an iterable of vertices

## itu.algs4.graphs.depth_first_paths module¶

class `itu.algs4.graphs.depth_first_paths.``DepthFirstPaths`(G, s)

Bases: `object`

The DepthFirstPaths class represents a data type for finding paths from a source vertex s to every other vertex in an undirected graph.

This implementation uses depth-first search. The constructor takes time proportional to V + E, where V is the number of vertices and E is the number of edges. Each call to hasPathTo(int) takes constant time each call to pathTo(int) takes time proportional to the length of the path. It uses extra space (not including the graph) proportional to V.

`has_path_to`(v)

Is there a path between the source vertex s and vertex v?

Parameters: v – the vertex true if there is a path, false otherwise ValueError – unless 0 <= v < V
`path_to`(v)

Returns a path between the source vertex s and vertex v, or None if no such path.

Parameters: v – the vertex the sequence of vertices on a path between the source vertex s and vertex v, as an Iterable ValueError – unless 0 <= v < V

## itu.algs4.graphs.digraph module¶

This module implements the directed graph data structure described in Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.

class `itu.algs4.graphs.digraph.``Digraph`(V)

Bases: `object`

The Graph class represents an undirected graph of vertices.

named 0 through V - 1. It supports the following two primary operations: add an edge to the graph, iterate over all of the vertices adjacent to a vertex. It also provides methods for returning the number of vertices V and the number of edges E. Parallel edges and self-loops are permitted. By convention, a self-loop v-v appears in the adjacency list of v twice and contributes two to the degree of v.

This implementation uses an adjacency-lists representation, which is a vertex-indexed array of Bag objects. All operations take constant time (in the worst case) except iterating over the vertices adjacent to a given vertex, which takes time proportional to the number of such vertices.

`E`()

Returns the number of edges in this graph.

Returns: the number of edges in this graph.
`V`()

Returns the number of vertices in this graph.

Returns: the number of vertices in this graph.
`add_edge`(v, w)

Adds the undirected edge v-w to this graph.

Parameters: v – one vertex in the edge w – the other vertex in the edge ValueError – unless both 0 <= v < V and 0 <= w < V
`adj`(v)

Returns the vertices adjacent to vertex v.

Parameters: v – the vertex the vertices adjacent to vertex v, as an iterable ValueError – unless 0 <= v < V
`degree`(v)

Returns the degree of vertex v.

Parameters: v – the vertex the degree of vertex v ValueError – unless 0 <= v < V
static `from_graph`(G)

Initializes a new graph that is a deep copy of G.

Parameters: G – the graph to copy copy of G
static `from_stream`(stream)

Initializes a graph from the specified input stream. The format is the number of vertices V, followed by the number of edges E, followed by E pairs of vertices, with each entry separated by whitespace.

Parameters: stream – the input stream new graph from stream ValueError – if the endpoints of any edge are not in prescribed range ValueError – if the number of vertices or edges is negative ValueError – if the input stream is in the wrong format
`reverse`()

Returns the reverse of the digraph.

Returns: the reverse of the digraph

## itu.algs4.graphs.dijkstra_all_pairs_sp module¶

This module implements a data type for solving the all-pairs shortest paths problem in edge-weighted digraphs where the edge weights are nonnegative.

class `itu.algs4.graphs.dijkstra_all_pairs_sp.``DijkstraAllPairsSP`(edge_weighted_digraph)

Bases: `object`

This implementation runs Dijkstra’s algorithm from each vertex. The constructor takes time proportional to V (E log V) and uses space proprtional to V2, where V is the number of vertices and E is the number of edges. Afterwards, the dist() and hasPath() methods take constant time and the path() method takes time proportional to the number of edges in the shortest path returned.

For additional documentation, see Section 4.4 of Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.

`dist`(source, target)

Returns the length of a shortest path from the source vertex to the target vertex.

Parameters: source – the source vertex target – the target vertex the length of a shortest path from the source vertex to the target vertex; float(‘inf’) if no such path
`has_path`(source, target)

Is there a path from the source vertex to the target vertex?

Parameters: source – the source vertex target – the target vertex True if there is a path from the source to the target, and False otherwise
`path`(source, target)

Returns a shortest path from source vertex to the target vertex.

Parameters: source – the source vertex target – the destination vertex a shortest path from the source vertex to the target vertex as an iterable of edges, and None if no such path

## itu.algs4.graphs.dijkstra_sp module¶

class `itu.algs4.graphs.dijkstra_sp.``DijkstraSP`(G, s)

Bases: `object`

The DijkstraSP class represents a data type for solving the single- source shortest paths problem in edge-weighted digraphs where the edge weights are nonnegative.

This implementation uses Dijkstra’s algorithm with a binary heap. The constructor takes time proportional to E log V, where V is the number of vertices and E is the number of edges. Each call to dist_to() and has_path_to() takes constant time. Each call to path_to() takes time proportional to the number of edges in the shortest path returned.

`dist_to`(v)

Returns the length of a shortest path from the source vertex s to vertex v.

Parameters: v – the destination vertex the length of a shortest path from the source vertex s to vertex v float IllegalArgumentException – unless 0 <= v < V
`has_path_to`(v)

Returns True if there is a ath from the source vertex s to vertex v.

Parameters: v – the destination vertex True if there is a path from the source vertex

s to vertex v. Otherwise returns False :rtype: bool :raises IllegalArgumentException: unless 0 <= v < V

`path_to`(v)

Returns a shortest path from the source vertex s to vertex v.

Parameters: v – the destination vertex a shortest path from the source vertex s to vertex v collections.iterable[DirectedEdge] IllegalArgumentException – unless 0 <= v < V
`itu.algs4.graphs.dijkstra_sp.``main`()

Creates an EdgeWeightedDigraph from input file.

Runs DijkstraSP on the graph with the given source vertex. Prints the shortest path from the source vertex to all other vertices.

## itu.algs4.graphs.dijkstra_undirected_sp module¶

class `itu.algs4.graphs.dijkstra_undirected_sp.``DijkstraUndirectedSP`(G, s)

Bases: `object`

The DijkstraSP class represents a data type for solving the single- source shortest paths problem in edge-weighted diagraphs where the edge weights are nonnegative.

This implementation uses Dijkstra’s algorithm with a binary heap. The constructor takes time proportional to E log V, where V is the number of vertices and E is the number of edges. Each call to dist_to() and has_path_to() takes constant time each call to path_to() takes time proportional to the number of edges in the shortest path returned.

`dist_to`(v)

Returns the length of a shortest path between the source vertex s and vertex v.

Parameters: v – the destination vertex the length of a shortest path between the source vertex s and

the vertex v. float(‘inf’) is not such path :rtype: float :raises IllegalArgumentException: unless 0 <= v < V

`has_path_to`(v)

Returns true if there is a path between the source vertex s and vertex v.

Parameters: v – the destination vertex True if there is a path between the source vertex

s to vertex v. False otherwise :rtype: bool

`path_to`(v)

Returns a shortest path between the source vertex s and vertex v.

Parameters: v – the destination vertex a shortest path between the source vertex s and vertex v.

None if no such path :rtype: collections.iterable[Edge] :raises IllegalArgumentException: unless 0 <= v < V

`itu.algs4.graphs.dijkstra_undirected_sp.``main`()

## itu.algs4.graphs.directed_cycle module¶

This module implements the directed cycle algorithm described in Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne. This version works for both weighted and unweighted directed graphs, due to Python’s duck-typing.

class `itu.algs4.graphs.directed_cycle.``DirectedCycle`(digraph)

Bases: `object`

The DirectedCycle class represents a data type for determining whether a digraph has a directed cycle. The hasCycle operation determines whether the digraph has a directed cycle and, and of so, the cycle operation returns one.

This implementation uses depth-first search. The constructor takes time proportional to V + E (in the worst case), where V is the number of vertices and E is the number of edges. Afterwards, the hasCycle operation takes constant time; the cycle operation takes time proportional to the length of the cycle.

See Topological to compute a topological order if the digraph is acyclic.

For additional documentation, see Section 4.2 of Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.

`cycle`()

Returns a directed cycle if the digraph has a directed cycle, and null otherwise.

Returns: a directed cycle (as an iterable) if the digraph has a directed cycle, and null otherwise
`has_cycle`()

Does the digraph have a directed cycle?

Returns: true if there is a cycle, false otherwise

## itu.algs4.graphs.directed_dfs module¶

class `itu.algs4.graphs.directed_dfs.``DirectedDFS`(G, *s)

Bases: `object`

The DirectedDFS class represents a data type for determining the vertices reachable from a given source vertex s (or a set of source vertices) in a digraph. For versions that find the paths, see DepthFirstDirectedPaths and BreadthFirstDirectedPaths.

This implementation uses depth-first search. The constructor takes time proportional to V + E (in the worst case), where V is the number of vertices and E is the number of edges.

For additional documentation, see Section 4.2 of Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.

`count`()

Returns the number of vertices reachable from the source vertex (or source vertices) :returns: the number of vertices reachable from the source vertex (or source vertices)

`is_marked`(v)

Is there a directed path from the source vertex and vertex v?

Parameters: v – the vertex True if there is a directed
`itu.algs4.graphs.directed_dfs.``main`()

Unit tests the DirectedDFS data type.

## itu.algs4.graphs.directed_edge module¶

class `itu.algs4.graphs.directed_edge.``DirectedEdge`(v, w, weight)

Bases: `object`

The DirectedEdge class represents a weighted edge in an EdgeWeightedDigraph.

Each edge consists of two integers (naming the two vertices) and a real-value weight. The data type provides methods for accessing the two endpoints of the directed edge and the weight.

`from_vertex`()

Returns the tail vertex of the directed edge.

Returns: the tail vertex of the directed edge int
`to_vertex`()

Returns the head vertex of the directed edge.

Returns: the head vertex of the directed edge int
`weight`()

Returns the weight of the directed edge.

Returns: the weight of the directed edge float
`itu.algs4.graphs.directed_edge.``main`()

Creates a directed edge and prints it.

## itu.algs4.graphs.edge module¶

class `itu.algs4.graphs.edge.``Edge`(v, w, weight)

Bases: `object`

The Edge class represents a weighted edge in an EdgeWeightedGraph.

Each edge consists of two integers (naming the two vertices) and a real-value weight. The data type provides methods for accessing the two endpoints of the edge and the weight. The natural order for this data type is by ascending order of weight.

`either`()

Returns either endpoint of this edge.

Returns: either endpoint of this edge int
`other`(vertex)

Returns the endpoint of this edge that is different from the given vertex.

Parameters: vertex – one endpoint of this edge the other endpoint of this edge int IllegalArgumentException – if the vertex is not one of the endpoints of this edge
`weight`()

Returns the weight of this edge.

Returns: the weight of this edge float
`itu.algs4.graphs.edge.``main`()

Creates an edge and prints it.

## itu.algs4.graphs.edge_weighted_digraph module¶

class `itu.algs4.graphs.edge_weighted_digraph.``EdgeWeightedDigraph`(V)

Bases: `object`

The EdgeWeightedDigraph class represents an edge-weighted digraph of vertices named 0 through V-1, where each directed edge is of type DirectedEdge and has a real-valued weight.

It supports the following two primary operations: add a directed edge to the digraph and iterate over all edges incident from a given vertex. it also provides methods for returning the number of vertices V and the number of edges E. Parallel edges and self-loops are permitted. This implementation uses an adjacency-lists representation, which is a vertex-indexed array of Bag objects. All operations take constant time (in the worst case) except iterating over the edges incident from a given vertex, which takes time proportional to the number of such edges.

`E`()

Returns the number of edges in this edge-weighted digraph.

Returns: the number of edges in this edge-weighted digraph int
`V`()

Returns the number of vertices in this edge-weighted digraph.

Returns: the number of vertices in this edge-weighted digraph int
`add_edge`(e)

Adds the directed edge e to this edge-weighted digraph.

Parameters: e – the edge IllegalArgumentException – unless endpoints of edge are between 0 and V-1
`adj`(v)

Returns the directed edges incident from vertex v.

Parameters: v – the vertex the directed edges incident from vertex v. collections.iterable[DirectedEdge] IllegalArgumentException – unless 0 <= v < V
`edges`()

Returns all directed edges in this edge-weighted digraph.

Returns: all edges in this edge-weighted digraph collections.iterable[DirectedEdge]
static `from_graph`(G)

Initializes a new edge-weighted digraph that is a deep copy of G.

Parameters: G – the edge-weighted digraph to copy a copy of graph G EdgeWeightedDigraph
static `from_stream`(stream)

Initializes an edge-weighted digraph from the specified input stream. The format is the number of vertices V, followed by the number of edges E, followed by E pairs of vertices and edge weights, with each entry seperated by whitespace.

Parameters: stream – the input stream IllegalArgumentException – if the endpoints of any edge are not in prescribed range IllegalArgumentException – if the number of vertices or edges is negative the edge-weighted digraph EdgeWeightedDigraph
`indegree`(v)

Returns the number of directed edges incident to vertex v. This is known as the indegree of vertex v.

Parameters: v – the vertex the indegree of vertex v int IllegalArgumentException – unless 0 <= v < V
`outdegree`(v)

Returns the number of directed edges incident from vertex v. This is known as the outdegree of vertex v.

Parameters: v – the vertex the outdegree of vertex v int IllegalArgumentException – unless 0 <= v < V
`itu.algs4.graphs.edge_weighted_digraph.``main`()

Creates an edge-weighted digraph from the given input file and prints it.

## itu.algs4.graphs.edge_weighted_directed_cycle module¶

class `itu.algs4.graphs.edge_weighted_directed_cycle.``EdgeWeightedDirectedCycle`(G)

Bases: `object`

Determines whether the edge-weighted digraph G has a directed cycle and, if so, finds such a cycle.

:param G the edge-weighted digraph

`cycle`()
`has_cycle`()
`itu.algs4.graphs.edge_weighted_directed_cycle.``main`(args)

## itu.algs4.graphs.edge_weighted_directed_cycle_anton module¶

This module implements the directed cycle algorithm for EdgeWeightedDigraphs described in Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne. This version works for both weighted and unweighted directed graphs, due to Python’s duck-typing.

class `itu.algs4.graphs.edge_weighted_directed_cycle_anton.``EdgeWeightedDirectedCycle`(edge_weighted_digraph)

Bases: `object`

The EdgeWeightedDirectedCycle class represents a data type for determining whether edge-weighted digraph has a directed cycle. The hasCycle operation determines whether the edge-weighted digraph has a directed cycle and, if so, the cycle operation returns one.

This implementation uses depth-first search. The constructor takes time proportional to V + E (in the worst case), where V is the number of vertices and E is the number of edges. Afterwards, the hasCycle operation takes constant time; the cycle operation takes time proportional to the length of the cycle.

See Topological to compute a topological order if the edge-weighted digraph is acyclic.

For additional documentation, see Section 4.4 of Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.

`cycle`()

Returns a directed cycle if the edge weighted digraph has a directed cycle, and null otherwise.

Returns: a directed cycle (as an iterable) if the digraph has a directed cycle, and null otherwise
`has_cycle`()

Does the edge weighted digraph have a directed cycle?

Returns: true if there is a cycle, false otherwise

## itu.algs4.graphs.edge_weighted_graph module¶

class `itu.algs4.graphs.edge_weighted_graph.``EdgeWeightedGraph`(V)

Bases: `object`

The EdgeWeightedGraph class represents an edge-weighted graph of vertices named 0 through V-1, where each undirected edge is of type Edge and has a real-valued weight.

It supports the following two primary operations: add an edge to the graph, iterate over all of the edges incident to a vertex. It also provides methods for returning the number of vertices V and the number of edges E. Parallel edges and self-loops are permitted. By convention, a self-loop v-v appears in the adjacency list of v twice and contributes two to the degree of v. This implementation uses an adjacency-list representation, which is a vertex-indexed array of Bag objects. All operations take constant time (in the worst case) except iterating over the edges incident to a given vertex, which takes time proportional to the number of such edges.

`E`()

Returns the number of edges in this edge-weighted graph.

Returns: the number of edges in this edge-weighted graph int
`V`()

Returns the number of vertices in this edge-weighted graph.

Returns: the number of vertices in this edge-weighted graph int
`add_edge`(e)

Adds the undirected edge e to this edge-weighted graph.

Parameters: e – the edge
`adj`(v)

Returns the edges incident on vertex v.

Parameters: v – the vertex the edges incident on vertex v collections.iterable[Edge]
`degree`(v)

Returns the degree of vertex v.

Parameters: v – the vertex the degree of vertex v int IllegalArgumentException – unless 0 <= v < V
`edges`()

Returns all edges in this edge-weighted graph.

Returns: all edges in this edge-weighted graph
static `from_graph`(G)

Initializes a new edge-weighted graph that is a deep copy of G.

Parameters: G – the edge-weighted graph to copy the copy of the graph edge-weighted graph G EdgeWeightedGraph
static `from_stream`(stream)

Initializes an edge-weighted graph from an input stream. The format is the number of vertices V, followed by the number of edges E, followed by E pairs of vertices and edge weights, with each entry separated by whitespace.

Parameters: stream – the input stream IllegalArgumentException – if the endpoints of any edge are not in prescribed range IllegalArgumentException – if the number of vertices or edges is negative the edge-weighted graph EdgeWeightedGraph
`itu.algs4.graphs.edge_weighted_graph.``main`()

Creates an edge-weighted graph from the given input file and prints it.

## itu.algs4.graphs.graph module¶

class `itu.algs4.graphs.graph.``Graph`(V)

Bases: `object`

The Graph class represents an undirected graph of vertices.

named 0 through V - 1. It supports the following two primary operations: add an edge to the graph, iterate over all of the vertices adjacent to a vertex. It also provides methods for returning the number of vertices V and the number of edges E. Parallel edges and self-loops are permitted. By convention, a self-loop v-v appears in the adjacency list of v twice and contributes two to the degree of v.

This implementation uses an adjacency-lists representation, which is a vertex-indexed array of Bag objects. All operations take constant time (in the worst case) except iterating over the vertices adjacent to a given vertex, which takes time proportional to the number of such vertices.

`E`()

Returns the number of edges in this graph.

Returns: the number of edges in this graph.
`V`()

Returns the number of vertices in this graph.

Returns: the number of vertices in this graph.
`add_edge`(v, w)

Adds the undirected edge v-w to this graph.

Parameters: v – one vertex in the edge w – the other vertex in the edge ValueError – unless both 0 <= v < V and 0 <= w < V
`adj`(v)

Returns the vertices adjacent to vertex v.

Parameters: v – the vertex the vertices adjacent to vertex v, as an iterable ValueError – unless 0 <= v < V
`degree`(v)

Returns the degree of vertex v.

Parameters: v – the vertex the degree of vertex v ValueError – unless 0 <= v < V
static `from_graph`(G)

Initializes a new graph that is a deep copy of G.

Parameters: G – the graph to copy copy of G
static `from_stream`(stream)

Initializes a graph from the specified input stream. The format is the number of vertices V, followed by the number of edges E, followed by E pairs of vertices, with each entry separated by whitespace.

Parameters: stream – the input stream new graph from stream ValueError – if the endpoints of any edge are not in prescribed range ValueError – if the number of vertices or edges is negative ValueError – if the input stream is in the wrong format

## itu.algs4.graphs.kosaraju_sharir_scc module¶

• Execution: python kosaraju_sharir_scc.py filename.txt
• Dependencies: Digraph TransitiveClosure InStream DepthFirstOrder
• Data files: https:#algs4.cs.princeton.edu/42digraph/tinyDG.txt
• https:#algs4.cs.princeton.edu/42digraph/mediumDG.txt
• https:#algs4.cs.princeton.edu/42digraph/largeDG.txt
• Compute the strongly-connected components of a digraph using the
• Kosaraju-Sharir algorithm.
• Runs in O(E + V) time.
• % python kosaraju_sharir_scc.py tinyDG.txt
• 5 strong components
• 1
• 0 2 3 4 5
• 9 10 11 12
• 6 8
• 7
class `itu.algs4.graphs.kosaraju_sharir_scc.``KosarajuSharirSCC`(G)

Bases: `object`

• Computes the strong components of the digraph G.
• @param G the digraph
`count`()
`id`(v)
`strongly_connected`(v, w)
`itu.algs4.graphs.kosaraju_sharir_scc.``main`(args)

## itu.algs4.graphs.kruskal_mst module¶

class `itu.algs4.graphs.kruskal_mst.``KruskalMST`(G)

Bases: `object`

The KruskalMST class represents a data type for computing a minimum spanning tree in an edge-weighted graph.

The edge weights can be positive, zero, or negative and need not be distinct. If the graph is not connected, it computes a minimum spanning forest, which is the union of minimum spanning trees in each connected component. The weight method returns the weight of a minimum spanning tree and the edges method returns its edges. This implementation uses Kruskal’s algorithm and the union-find data type. The constructor takes time proportional to E log E and extra space (not including the graph) proportional to V, where V is the number of vertices and E is the number of edges- Afterwards, the weight method takes constant time and the edges method takes time proportional to V.

`edges`()

Returns the edges in a minimum spanning tree (or forest).

Returns: the edges in a minimum spanning tree (or forest)
`weight`()

Returns the sum of the edge weights in a minimum spanning tree (or forest).

Returns: the sum of the edge weights in a minimum spanning tree (or forest)
`itu.algs4.graphs.kruskal_mst.``main`()

Creates an edge-weighted graph from an input file, runs Kruskal’s algorithm on it, and prints the edges of the MST and the sum of the edge weights.

## itu.algs4.graphs.lazy_prim_mst module¶

class `itu.algs4.graphs.lazy_prim_mst.``LazyPrimMST`(G)

Bases: `object`

The LazyPrimMST class represents a data type for computing a minimum spanning tree in an edge-weighted graph. The edge weights can be positive, zero, or negative and need not be distinct. If the graph is not connected, it computes a minimum spanning forest, which is the union of minimum spanning trees in each connected component. The weight() method returns the weight of a minimum spanning tree and the edges() method returns its edges.

This implementation uses a lazy version of Prim’s algorithm with a binary heap of edges. The constructor takes time proportional to E log E and extra space (not including the graph) proportional to E, where V is the number of vertices and E is the number of edges. Afterwards, the weight() method takes constant time and the edges() method takes time proportional to V.

`FLOATING_POINT_EPSILON` = 1e-12
`edges`()

Returns the edges in a minimum spanning tree (or forest).

Returns: the edges in a minimum spanning tree (or forest) as an iterable of edges
`weight`()

Returns the sum of the edge weights in a minimum spanning tree (or forest).

Returns: the sum of the edge weights in a minimum spanning tree (or forest)

## itu.algs4.graphs.prim_mst module¶

class `itu.algs4.graphs.prim_mst.``PrimMST`(G)

Bases: `object`

The PrimMST class represents a data type for computing a minimum spanning tree in an edge-weighted graph. The edge weights can be positive, zero, or negative and need not be distinct. If the graph is not connected, it computes a minimum spanning forest, which is the union of minimum spanning trees in each connected component. The weight() method returns the weight of a minimum spanning tree and the edges() method returns its edges.

This implementation uses Prim’s algorithm with an indexed binary heap. The constructor takes time proportional to E log V and extra space not including the graph) proportional to V, where V is the number of vertices and E is the number of edges. Afterwards, the weight() method takes constant time and the edges() method takes time proportional to V.

`FLOATING_POINT_EPSILON` = 1e-12
`edges`()

Returns the edges in a minimum spanning tree (or forest).

Returns: the edges in a minimum spanning tree (or forest) as an iterable of edges
`weight`()

Returns the sum of the edge weights in a minimum spanning tree (or forest).

Returns: the sum of the edge weights in a minimum spanning tree (or forest)

## itu.algs4.graphs.symbol_digraph module¶

class `itu.algs4.graphs.symbol_digraph.``SymbolDigraph`(filename, delimiter)

Bases: `object`

The SymbolDigraph class representsclass represents a digraph, where the vertex names are arbitrary strings. By providing mappings between vertex names and integers, it serves as a wrapper around the Digraph data type, which assumes the.

vertex names are integers between 0 and V - 1. It also supports initializing a symbol digraph from a file.

This implementation uses an ST to map from strings to integers, an array to map from integers to strings, and a Digraph to store the underlying graph. The index_of and contains operations take time proportional to log V, where V is the number of vertices. The name_of operation takes constant time.

`contains`(s)

Does the graph contain the vertex named s?

Parameters: s – the name of a vertex

:return:s true if s is the name of a vertex, and false otherwise

`digraph`()
`index_of`(s)

Returns the integer associated with the vertex named s.

Parameters: s – the name of a vertex the integer (between 0 and V - 1) associated with the vertex named s
`name_of`(v)

Returns the name of the vertex associated with the integer v.

@param v the integer corresponding to a vertex (between 0 and V - 1) @throws IllegalArgumentException unless 0 <= v < V @return the name of the vertex associated with the integer v

## itu.algs4.graphs.symbol_graph module¶

class `itu.algs4.graphs.symbol_graph.``SymbolGraph`(filename, delimiter)

Bases: `object`

The SymbolGraph class represents an undirected graph, where the vertex names are arbitrary strings. By providing mappings between vertex names and integers, it serves as a wrapper around the Graph data type, which assumes the vertex names are integers.

between 0 and V - 1. It also supports initializing a symbol graph from a file.

This implementation uses an ST to map from strings to integers, an array to map from integers to strings, and a Graph to store the underlying graph. The index_of and contains operations take time proportional to log V, where V is the number of vertices. The name_of operation takes constant time.

`contains`(s)

Does the graph contain the vertex named s?

Parameters: s – the name of a vertex

:return:s true if s is the name of a vertex, and false otherwise

`graph`()
`index_of`(s)

Returns the integer associated with the vertex named s.

Parameters: s – the name of a vertex the integer (between 0 and V - 1) associated with the vertex named s
`name_of`(v)

Returns the name of the vertex associated with the integer v.

@param v the integer corresponding to a vertex (between 0 and V - 1) @throws IllegalArgumentException unless 0 <= v < V @return the name of the vertex associated with the integer v

## itu.algs4.graphs.topological module¶

This module implements the topological order algorithm described in Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.

class `itu.algs4.graphs.topological.``Topological`(digraph)

Bases: `object`

The Topological class represents a data type for determining a topological order of a directed acyclic graph (DAG). Recall, a digraph has a topological order if and only if it is a DAG. The hasOrder operation determines whether the digraph has a topological order, and if so, the order operation returns one.

This implementation uses depth-first search. The constructor takes time proportional to V + E (in the worst case), where V is the number of vertices and E is the number of edges. Afterwards, the hasOrder and rank operations takes constant time the order operation takes time proportional to V.

See DirectedCycle, DirectedCycleX, and EdgeWeightedDirectedCycle to compute a directed cycle if the digraph is not a DAG. See TopologicalX for a nonrecursive queue-based algorithm to compute a topological order of a DAG.

For additional documentation, see Section 4.2 of Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.

`has_order`()

Does the digraph have a topological order?

Returns: True if the digraph has a topological order (or equivalently, if the digraph is a DAG), and False otherwise
`order`()

Returns a topological order if the digraph has a topologial order, and None otherwise.

Returns: a topological order of the vertices (as an interable) if the digraph has a topological order (or equivalently, if the digraph is a DAG), and None otherwise
`rank`(v)

The the rank of vertex v in the topological order -1 if the digraph is not a DAG.

Parameters: v – the vertex the position of vertex v in a topological order of the digraph -1 if the digraph is not a DAG

## itu.algs4.graphs.transitive_closure module¶

• Execution: python transitive_closure.py filename.txt
• Dependencies: Digraph DirectedDFS
• Data files: https:#algs4.cs.princeton.edu/42digraph/tinyDG.txt
• Compute transitive closure of a digraph and support
• reachability queries.
• Preprocessing time: O(V(E + V)) time.
• Query time: O(1).
• Space: O(V^2).
• % python transitive_closure.py tinyDG.txt
• 0 1 2 3 4 5 6 7 8 9 10 11 12
• 0: T T T T T T
• 1: T
• 2: T T T T T T
• 3: T T T T T T
• 4: T T T T T T
• 5: T T T T T T
• 6: T T T T T T T T T T T
• 7: T T T T T T T T T T T T T
• 8: T T T T T T T T T T T T T
• 9: T T T T T T T T T T
• 10: T T T T T T T T T T
• 11: T T T T T T T T T T
• 12: T T T T T T T T T T
class `itu.algs4.graphs.transitive_closure.``TransitiveClosure`(G)

Bases: `object`

• Computes the transitive closure of the digraph G.
• @param G the digraph
`reachable`(v, w)
`itu.algs4.graphs.transitive_closure.``main`(args)