How does edge_dfs differ from dfs_edges?

The former visits edges, including connections to already visited nodes; the latter reports node-discovery edges.

Can it process an undirected graph?

Yes. Each represented undirected edge remains one connection even though it can be approached from either endpoint.

Does a fixed source guarantee every edge is returned?

No. Reachability and direction can leave parts of the graph outside that traversal.

AI Glossary / Graphs and symbolic AI / Advanced

Depth First Search on Edges

Definition

Depth First Search on Edges is a traversal that explores graph connections in depth-first order while tracking edges as the items to visit. In the supplied NetworkX context, edge_dfs reports edges even when their destination nodes have already been encountered. This differs from a node-based DFS discovery tree, which records only the links used to discover new nodes.

What it means

Knowing that every reachable node has been visited does not mean every connection has been reported. A service graph can contain a return link, an additional route between known services, or several distinct connections between the same pair. An edge-focused traversal keeps those relationships visible.
The traversal is still depth first: it follows available connections before returning to alternatives. However, its coverage objective concerns edges, not just discovering nodes.
The output is a traversal sequence, not necessarily a single continuous route that can be executed without backtracking. It is also not automatically an Eulerian trail, a shortest route, or a proof that the modeled connections are operationally valid.

How it works

The traversal maintains exploration state and records which edges have been visited. Encountering an already known endpoint does not automatically suppress an unvisited edge. Backtracking allows exploration to resume where other connections remain.
NetworkX supports directed and undirected graphs, including multigraphs. In a multigraph, an edge key distinguishes parallel connections. Direction settings matter: original follows directed edges, reverse traverses them backward, and ignore treats them as undirected for traversal. Reported directed-edge endpoints retain the stored edge orientation, with traversal-direction information added when requested.
The starting point controls coverage. A specified source can leave unreachable edges unvisited. With no source specified, the function selects additional starting nodes as needed to search the graph's edges. Coverage claims must match these choices.

Three practical examples

Integration inventory: A team inspects all represented connections reachable from an application. A return connection between already discovered services still matters because it may carry a distinct request flow. A discovery tree alone could omit it.
Transport modeling: Two terminals have multiple modeled links operated under different arrangements. A multigraph preserves those links with distinct identities. Collapsing them into one simple edge before traversal would lose information that the traversal cannot recover.
Workflow review: Analysts inspect transitions among process states, including loops returning to an earlier state. They use edge coverage to review the transition inventory, while separately checking whether any transition is feasible under its conditions.

Think of it this way

Imagine checking roads rather than merely ticking off towns on a map. Reaching every town does not mean you have listed every road between them. An edge-focused inspection records additional roads even when both endpoints are already familiar. The inspection order is not necessarily a practical driving itinerary.

Worked example

Consider an invented directed graph with nodes A, B, C, and D. Its edges are A→B, B→C, C→B, and B→D. Start at A and inspect B's outgoing neighbors in the order C, then D.
A node-discovery DFS follows A→B and B→C. At C, the destination B has already been discovered, so C→B does not become a discovery-tree edge. After backtracking, B→D discovers D. The discovery tree therefore contains three edges for four nodes.
An edge-focused DFS reports A→B, B→C, C→B, and B→D under this ordering. It includes the return connection C→B even though B is already known. The graph has four edges, and all four are reachable under the stated direction and starting point.
Now add E→A, with E a new node. Starting from A and respecting edge direction does not reach E or its outgoing edge E→A. Ignoring orientation can make that connection traversable backward, but this changes the traversal question; it does not change the stored edge into A→E.
Finally, suppose B→D represents two distinct links in a directed multigraph. Their separate keys must be retained if both are to appear as distinct connections. The example's counts depend on whether the data model stores one edge or two.

Illustrative case study

Fictional Willow Integrations builds a report of connections among its internal services. The report initially uses a DFS discovery tree and labels it “all integrations.” Reviewers notice that a feedback connection between two already discovered services is missing.
The team switches the inspection to edge-focused traversal and retains distinct identifiers for parallel integrations. It also documents the source and direction settings. A separate check covers components that cannot be reached from the main application.
The revised report makes its coverage claim more precise. It still cannot establish that the inventory is complete in the real environment or that each recorded integration works. Those questions require comparison with deployment evidence and operational checks. This is an illustrative scenario, not a measured customer case.

Common misconceptions and mistakes

“All nodes visited means all edges reported.” Additional links between known nodes can remain outside a discovery tree.
“Every returned edge discovers a new node.” Edge-focused traversal explicitly includes other edges.
“The sequence is an Eulerian trail.” Edge enumeration and a continuous trail are different requirements.
“Ignoring direction reverses the stored graph.” It changes traversal behavior, not the original relationship.
“Parallel links survive any graph representation.” A simple graph may already have collapsed them.

Business use

Choose edge-focused traversal when the question concerns relationships themselves: integrations, transitions, dependencies, or parallel connections. Define whether the inventory is limited to a reachable region or intended to cover the entire recorded graph.
Preserve direction, edge identity, and relevant metadata in the report. Test examples containing cycles, disconnected components, and parallel edges. Reconcile the returned count with the intended edge set, and avoid claiming full coverage based only on a count of visited nodes. Keep graph completeness separate from traversal completeness.

Check your understanding

Which edge does the example's discovery tree omit?

Answer: C→B.

Why is E→A missed when starting at A with original direction?

Answer: Its source E is not reachable from A.

What distinguishes two parallel B→D links?

Answer: Their separate edge identities or keys in the multigraph.

Related terms

Depth First Search
Directed graph
graph traversal
edge coverage
discovery tree
multigraph
reachability
Eulerian trail

Learn next

Draw a graph containing a return edge, an unreachable incoming edge, and parallel links. Compare node-discovery edges with edge-focused output, then explain how changing the source or orientation changes coverage.

Sources

NetworkX, edge_dfs, edge traversal, orientation, and multigraph behavior: https://networkx.org/documentation/stable/reference/algorithms/generated/networkx.algorithms.traversal.edgedfs.edge_dfs.html NetworkX, dfs_edges, node-discovery traversal and coverage: https://networkx.org/documentation/stable/reference/algorithms/generated/networkx.algorithms.traversal.depth_first_search.dfs_edges.html

Previous: Depth First Search Next: Depth image