liveBook · Manning

Edge

As explained in The Coder Cafe

An edge is a directed connection between two vertices that carries flow and has a capacity limit.

An edge is a connection between two vertices, or nodes, in a graph. It may be directed, as when one person follows another, or undirected, as with a mutual friendship. The direction matters: an edge from A to B does not by itself establish an edge from B to A. section 1.3

An edge can carry different information depending on the problem:

  • A weighted edge has an associated value, such as travel time between cities; an unweighted edge does not distinguish connections by weight. section 1.3
  • A dependency edge links tasks in a directed acyclic graph. Incoming edges contribute to a vertex’s in-degree, which topological sort uses to find an execution order. section 1.4.1
  • A flow-network edge has a capacity: the most flow it can carry. A path can carry additional flow only when every edge on it has capacity available. section 1.4.2

Finding a route for more flow

Suppose water travels from a reservoir toward homes through pipes with different capacities. A connected route is not necessarily an augmenting path: if one pipe has no capacity left, no additional water can pass along that entire route. The same constraint applies to bandwidth-limited connections in a data network. section 1.4.2

How edges are stored affects the cost of finding one. An adjacency matrix records whether an edge from vertex i to vertex j exists, giving O(1) lookup but using O(v²) space. An adjacency list stores each vertex’s edges, using O(v + e) space but taking O(d) to search a vertex’s list, where d is its degree. Lists avoid much of a matrix’s wasted space in sparse graphs; matrices offer faster edge lookup in dense ones. section 1.3

How The Coder Cafe covers it

How deep it goes
Defines edge types and compares their storage costs, then applies capacity-limited edges to augmenting paths without specifying a general edge implementation.
Examples
Illustrates edges with social connections, travel times, job dependencies, water pipes, and bandwidth-limited data networks.
What it assumes
Defines vertices and edges from zero while using basic arrays, maps, and linked lists to compare graph storage.
What you can do after
Evaluate/understand whether a connection has direction, weight, or available capacity and choose a graph representation by lookup and space costs.
How it connects
Connects edges to vertices, adjacency matrices, adjacency lists, topological sort, and maximum flow.

Also explained in

Compare how 20 books explain edge →

Related concepts

This explainer was generated by Manning's knowledge graph from the text of The Coder Cafe. The section links point to the parts of the book it draws on.