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 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
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 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
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 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
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:
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

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 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
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
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
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
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
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 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
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.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 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
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 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
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 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
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 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
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 duck-typing.

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 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
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 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
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 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
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 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
Return type:int
V()

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

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

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

Parameters:e – the edge
Raises: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
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 edge-weighted digraph.

Returns:all edges in this edge-weighted digraph
Return type: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
Returns:a copy of graph G
Return type: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
Raises:
Returns:

the edge-weighted digraph
Return type:

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
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 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.

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 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
Return type:int
V()

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

Returns:the number of vertices in this edge-weighted graph
Return type: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
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 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
Returns:the copy of the graph edge-weighted graph G
Return type: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
Raises:
Returns:

the edge-weighted graph
Return type:

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
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 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
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 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
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)

Module contents