itu.algs4.graphs package¶
Submodules¶
itu.algs4.graphs.Arbitrage module¶
itu.algs4.graphs.CPM module¶
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 singlesource longest paths problem in edgeweighted directed acyclic graphs (DAGs). The edge weights can be positive, negative, or zero.
This implementation uses a topologicalsort 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 Returns: 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 Returns: 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 singlesource shortest paths problem in edgeweighted directed acyclic graphs (DAGs). The edge weights can be positive, negative, or zero.
This implementation uses a topologicalsort 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 Returns: the length of a shortest path from the source vertex s to vertex v math.inf if no such path Raises: 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 Returns: true if there is a path from the source vertex s to vertex v, and false otherwise Raises: 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 Returns: a shortest path from the source vertex s to vertex v as an iterable of edges, and None if no such path Raises: 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 oddlength 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 depthfirst 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 breadthfirst search.

exception
UnsupportedOperationException
¶ Bases:
Exception

color
(v)¶ Returns the side of the bipartite that vertex v is on.
Parameters: v – the vertex
Returns: 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
Raises:  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 oddlength cycle if the graph is not bipartite, and None otherwise.
Returns: an oddlength cycle if the graph is not bipartite (and hence has an oddlength cycle), and None otherwise

exception
itu.algs4.graphs.breadth_first_paths module¶

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 breadthfirst 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 Returns: the number of edges in a shortest path Raises: 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 Returns: true if there is a path, and False otherwise Raises: 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 Returns: the sequence of vertices on a shortest path, as an Iterable Raises: ValueError – unless 0 <= v < 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 depthfirst 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
Returns: True if vertices v and w are in the same connected component; False otherwise
Raises:  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 Returns: the component id of the connected component containing vertex v Raises: ValueError – unless 0 <= v < V

size
(v)¶ Returns the number of vertices in the connected component containing vertex v.
Parameters: v – the vertex Returns: the number of vertices in the connected component containing vertex v Raises: ValueError – unless 0 <= v < 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 depthfirst 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 commandline 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 commandline arguments

static
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 edgeweighted digraph, including preorder, postorder, and reverse postorder.
This implementation uses depthfirst 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 Returns: 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 Returns: 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 depthfirst 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 Returns: true if there is a path, false otherwise Raises: 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 Returns: the sequence of vertices on a path between the source vertex s and vertex v, as an Iterable Raises: ValueError – unless 0 <= v < V

itu.algs4.graphs.depth_first_search module¶

class
itu.algs4.graphs.depth_first_search.
DepthFirstSearch
(G, s)¶ Bases:
object
The DepthFirstSearch class represents a data type for determining the vertices connected to a given source vertex s in an undirected graph. For versions that find the paths, see DepthFirstPaths and BreadthFirstPaths.
This implementation uses depthfirst 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. It uses extra space (not including the graph) proportional to V.

count
()¶ Returns the number of vertices connected to the source vertex s.
Returns: the number of vertices connected to the source vertex s

marked
(v)¶ Is there a path between the source vertex s and vertex v?
Parameters: v – the vertex Returns: true if there is a path, false otherwise Raises: 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.
For more information, see chapter 4.2 of the book.

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 selfloops are permitted. By convention, a selfloop vv appears in the adjacency list of v twice and contributes two to the degree of v.
This implementation uses an adjacencylists representation, which is a vertexindexed 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 vw to this graph.
Parameters:  v – one vertex in the edge
 w – the other vertex in the edge
Raises: ValueError – unless both 0 <= v < V and 0 <= w < V

adj
(v)¶ Returns the vertices adjacent to vertex v.
Parameters: v – the vertex Returns: the vertices adjacent to vertex v, as an iterable Raises: ValueError – unless 0 <= v < V

degree
(v)¶ Returns the degree of vertex v.
Parameters: v – the vertex Returns: the degree of vertex v Raises: 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 Returns: 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
Returns: new graph from stream
Raises:  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 allpairs shortest paths problem in edgeweighted 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
Returns: 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
Returns: 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
Returns: 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 edgeweighted 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 Returns: the length of a shortest path from the source vertex s to vertex v Return type: float Raises: 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 Returns: 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 Returns: a shortest path from the source vertex s to vertex v Return type: collections.iterable[DirectedEdge] Raises: 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 edgeweighted 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 Returns: 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 Returns: 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 Returns: 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 ducktyping.
For more information, see chapter 4.2 of the book.

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 depthfirst 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 depthfirst 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 Returns: 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 realvalue 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 Return type: int

to_vertex
()¶ Returns the head vertex of the directed edge.
Returns: the head vertex of the directed edge Return type: int

weight
()¶ Returns the weight of the directed edge.
Returns: the weight of the directed edge Return type: float


itu.algs4.graphs.directed_edge.
main
()¶ Creates a directed edge and prints it.
Returns:
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 realvalue 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 Return type: int

other
(vertex)¶ Returns the endpoint of this edge that is different from the given vertex.
Parameters: vertex – one endpoint of this edge Returns: the other endpoint of this edge Return type: int Raises: 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 Return type: 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 edgeweighted digraph of vertices named 0 through V1, where each directed edge is of type DirectedEdge and has a realvalued 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 selfloops are permitted. This implementation uses an adjacencylists representation, which is a vertexindexed 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 edgeweighted digraph.
Returns: the number of edges in this edgeweighted digraph Return type: int

V
()¶ Returns the number of vertices in this edgeweighted digraph.
Returns: the number of vertices in this edgeweighted digraph Return type: int

add_edge
(e)¶ Adds the directed edge e to this edgeweighted digraph.
Parameters: e – the edge Raises: IllegalArgumentException – unless endpoints of edge are between 0 and V1

adj
(v)¶ Returns the directed edges incident from vertex v.
Parameters: v – the vertex Returns: the directed edges incident from vertex v. Return type: collections.iterable[DirectedEdge] Raises: IllegalArgumentException – unless 0 <= v < V

edges
()¶ Returns all directed edges in this edgeweighted digraph.
Returns: all edges in this edgeweighted digraph Return type: collections.iterable[DirectedEdge]

static
from_graph
(G)¶ Initializes a new edgeweighted digraph that is a deep copy of G.
Parameters: G – the edgeweighted digraph to copy Returns: a copy of graph G Return type: EdgeWeightedDigraph

static
from_stream
(stream)¶ Initializes an edgeweighted 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
Raises:  IllegalArgumentException – if the endpoints of any edge are not in prescribed range
 IllegalArgumentException – if the number of vertices or edges is negative
Returns: the edgeweighted digraph
Return type:

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 Returns: the indegree of vertex v Return type: int Raises: 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 Returns: the outdegree of vertex v Return type: int Raises: IllegalArgumentException – unless 0 <= v < V


itu.algs4.graphs.edge_weighted_digraph.
main
()¶ Creates an edgeweighted 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 edgeweighted digraph G has a directed cycle and, if so, finds such a cycle.
:param G the edgeweighted 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 ducktyping.
For more information, see chapter 4.2 of the book.

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 edgeweighted digraph has a directed cycle. The hasCycle operation determines whether the edgeweighted digraph has a directed cycle and, if so, the cycle operation returns one.
This implementation uses depthfirst 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 edgeweighted 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 edgeweighted graph of vertices named 0 through V1, where each undirected edge is of type Edge and has a realvalued 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 selfloops are permitted. By convention, a selfloop vv appears in the adjacency list of v twice and contributes two to the degree of v. This implementation uses an adjacencylist representation, which is a vertexindexed 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 edgeweighted graph.
Returns: the number of edges in this edgeweighted graph Return type: int

V
()¶ Returns the number of vertices in this edgeweighted graph.
Returns: the number of vertices in this edgeweighted graph Return type: int

add_edge
(e)¶ Adds the undirected edge e to this edgeweighted graph.
Parameters: e – the edge

adj
(v)¶ Returns the edges incident on vertex v.
Parameters: v – the vertex Returns: the edges incident on vertex v Return type: collections.iterable[Edge]

degree
(v)¶ Returns the degree of vertex v.
Parameters: v – the vertex Returns: the degree of vertex v Return type: int Raises: IllegalArgumentException – unless 0 <= v < V

edges
()¶ Returns all edges in this edgeweighted graph.
Returns: all edges in this edgeweighted graph

static
from_graph
(G)¶ Initializes a new edgeweighted graph that is a deep copy of G.
Parameters: G – the edgeweighted graph to copy Returns: the copy of the graph edgeweighted graph G Return type: EdgeWeightedGraph

static
from_stream
(stream)¶ Initializes an edgeweighted 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
Raises:  IllegalArgumentException – if the endpoints of any edge are not in prescribed range
 IllegalArgumentException – if the number of vertices or edges is negative
Returns: the edgeweighted graph
Return type:


itu.algs4.graphs.edge_weighted_graph.
main
()¶ Creates an edgeweighted 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 selfloops are permitted. By convention, a selfloop vv appears in the adjacency list of v twice and contributes two to the degree of v.
This implementation uses an adjacencylists representation, which is a vertexindexed 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 vw to this graph.
Parameters:  v – one vertex in the edge
 w – the other vertex in the edge
Raises: ValueError – unless both 0 <= v < V and 0 <= w < V

adj
(v)¶ Returns the vertices adjacent to vertex v.
Parameters: v – the vertex Returns: the vertices adjacent to vertex v, as an iterable Raises: ValueError – unless 0 <= v < V

degree
(v)¶ Returns the degree of vertex v.
Parameters: v – the vertex Returns: the degree of vertex v Raises: 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 Returns: 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
Returns: new graph from stream
Raises:  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 stronglyconnected components of a digraph using the
 KosarajuSharir 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 edgeweighted 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 unionfind 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 edgeweighted 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 edgeweighted 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
= 1e12¶

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 edgeweighted 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
= 1e12¶

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 Returns: 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 Returns: 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.
For more information, see chapter 4.2 of the book.

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 depthfirst 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 queuebased 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 Returns: 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)¶