18.14 Paths in Directed Acyclic Graphs

Module: sage.combinat.graph_path

Paths in Directed Acyclic Graphs

Module-level Functions

GraphPaths( g, [source=None], [target=None])

Returns the combinatorial class of paths in the directed acyclic graph g.

sage: G = DiGraph({1:[2,2,3], 2:[3,4], 3:[4], 4:[5,5]}, multiedges=True)

If source and target are not given, then the returned class contains all paths (including trivial paths containing only one vertex).

sage: p = GraphPaths(G); p
Paths in Multi-digraph on 5 vertices
sage: p.count()
37
sage: p.random_element()
[1, 2, 3, 4, 5]

If the source is specified, then the returned class contains all of the paths starting at the vertex source (including the trivial path).

sage: p = GraphPaths(G, source=3); p
Paths in Multi-digraph on 5 vertices starting at 3
sage: p.list()
[[3], [3, 4], [3, 4, 5], [3, 4, 5]]

If the target is specified, then the returned class contains all of the paths ending at the vertex target (including the trivial path).

sage: p = GraphPaths(G, target=3); p
Paths in Multi-digraph on 5 vertices ending at 3
sage: p.count()
5
sage: p.list()
[[3], [1, 3], [2, 3], [1, 2, 3], [1, 2, 3]]

If both the target and source are specified, then the returned class contains all of the paths from source to target.

sage: p = GraphPaths(G, source=1, target=3); p
Paths in Multi-digraph on 5 vertices starting at 1 and ending at 3
sage: p.count()
3
sage: p.list()
[[1, 2, 3], [1, 2, 3], [1, 3]]

Note that G must be a directed acyclic graph.

sage: G = DiGraph({1:[2,2,3,5], 2:[3,4], 3:[4], 4:[2,5,7], 5:[6]}, multiedges=True)
sage: GraphPaths(G)
Traceback (most recent call last):
...
TypeError: g must be a directed acyclic graph

Class: GraphPaths_all

class GraphPaths_all

sage: G = DiGraph({1:[2,2,3], 2:[3,4], 3:[4], 4:[5,5]}, multiedges=True)
sage: p = GraphPaths(G)
sage: p.count()
37

GraphPaths_all( self, g)

TESTS:

sage: G = DiGraph({1:[2,2,3], 2:[3,4], 3:[4], 4:[5,5]}, multiedges=True)
sage: p = GraphPaths(G)
sage: p == loads(dumps(p))
True

Functions: list

list( self)

Returns a list of the paths of self.

sage: G = DiGraph({1:[2,2,3], 2:[3,4], 3:[4], 4:[5,5]}, multiedges=True)
sage: len(GraphPaths(G).list())
37

Special Functions: __init__, $\,$ __repr__

__repr__( self)

TESTS:

sage: G = DiGraph({1:[2,2,3], 2:[3,4], 3:[4], 4:[5,5]}, multiedges=True)
sage: p = GraphPaths(G)
sage: repr(p)
'Paths in Multi-digraph on 5 vertices'

Class: GraphPaths_common

class GraphPaths_common

Functions: incoming_edges, $\,$ incoming_paths, $\,$ outgoing_edges, $\,$ outgoing_paths, $\,$ paths, $\,$ paths_from_source_to_target

incoming_edges( self, v)

Returns a list of v's incoming edges.

sage: G = DiGraph({1:[2,2,3], 2:[3,4], 3:[4], 4:[5,5]}, multiedges=True)
sage: p = GraphPaths(G)
sage: p.incoming_edges(2)
[(1, 2, None), (1, 2, None)]

incoming_paths( self, v)

Returns a list of paths that end at v.

sage: G = DiGraph({1:[2,2,3], 2:[3,4], 3:[4], 4:[5,5]}, multiedges=True)
sage: gp = GraphPaths(G)
sage: gp.incoming_paths(2)
[[2], [1, 2], [1, 2]]

outgoing_edges( self, v)

Returns a list of v's outgoing edges.

sage: G = DiGraph({1:[2,2,3], 2:[3,4], 3:[4], 4:[5,5]}, multiedges=True)
sage: p = GraphPaths(G)
sage: p.outgoing_edges(2)
[(2, 3, None), (2, 4, None)]

outgoing_paths( self, v)

Returns a list of the paths that start at v.

sage: G = DiGraph({1:[2,2,3], 2:[3,4], 3:[4], 4:[5,5]}, multiedges=True)
sage: gp = GraphPaths(G)
sage: gp.outgoing_paths(3)
[[3], [3, 4], [3, 4, 5], [3, 4, 5]]
sage: gp.outgoing_paths(2)
[[2],
 [2, 3],
 [2, 3, 4],
 [2, 3, 4, 5],
 [2, 3, 4, 5],
 [2, 4],
 [2, 4, 5],
 [2, 4, 5]]

paths( self)

Returns a list of all the paths of self.

sage: G = DiGraph({1:[2,2,3], 2:[3,4], 3:[4], 4:[5,5]}, multiedges=True)
sage: gp = GraphPaths(G)
sage: len(gp.paths())
37

paths_from_source_to_target( self, source, target)

Returns a list of paths from source to target.

sage: G = DiGraph({1:[2,2,3], 2:[3,4], 3:[4], 4:[5,5]}, multiedges=True)
sage: gp = GraphPaths(G)
sage: gp.paths_from_source_to_target(2,4)
[[2, 3, 4], [2, 4]]

Class: GraphPaths_s

class GraphPaths_s

GraphPaths_s( self, g, source)

TESTS:

sage: G = DiGraph({1:[2,2,3], 2:[3,4], 3:[4], 4:[5,5]}, multiedges=True)
sage: p = GraphPaths(G, 4)
sage: p == loads(dumps(p))
True

Functions: list

list( self)

sage: G = DiGraph({1:[2,2,3], 2:[3,4], 3:[4], 4:[5,5]}, multiedges=True)
sage: p = GraphPaths(G, 4)
sage: p.list()
[[4], [4, 5], [4, 5]]

Special Functions: __init__, $\,$ __repr__

__repr__( self)

TESTS:

sage: G = DiGraph({1:[2,2,3], 2:[3,4], 3:[4], 4:[5,5]}, multiedges=True)
sage: p = GraphPaths(G, 4)
sage: repr(p)
'Paths in Multi-digraph on 5 vertices starting at 4'

Class: GraphPaths_st

class GraphPaths_st

sage: G = DiGraph({1:[2,2,3], 2:[3,4], 3:[4], 4:[5,5]}, multiedges=True)
sage: GraphPaths(G,1,2).count()
2
sage: GraphPaths(G,1,3).count()
3
sage: GraphPaths(G,1,4).count()
5
sage: GraphPaths(G,1,5).count()
10
sage: GraphPaths(G,2,3).count()
1
sage: GraphPaths(G,2,4).count()
2
sage: GraphPaths(G,2,5).count()
4
sage: GraphPaths(G,3,4).count()
1
sage: GraphPaths(G,3,5).count()
2
sage: GraphPaths(G,4,5).count()
2

GraphPaths_st( self, g, source, target)

TESTS:

sage: G = DiGraph({1:[2,2,3], 2:[3,4], 3:[4], 4:[5,5]}, multiedges=True)
sage: p = GraphPaths(G,1,2)
sage: p == loads(dumps(p))
True

Functions: list

list( self)

sage: G = DiGraph({1:[2,2,3], 2:[3,4], 3:[4], 4:[5,5]}, multiedges=True)
sage: p = GraphPaths(G,1,2)
sage: p.list()
[[1, 2], [1, 2]]

Special Functions: __init__, $\,$ __repr__

__repr__( self)

TESTS:

sage: G = DiGraph({1:[2,2,3], 2:[3,4], 3:[4], 4:[5,5]}, multiedges=True)
sage: p = GraphPaths(G,1,2)
sage: repr(p)
'Paths in Multi-digraph on 5 vertices starting at 1 and ending at 2'

Class: GraphPaths_t

class GraphPaths_t

GraphPaths_t( self, g, target)

TESTS:

sage: G = DiGraph({1:[2,2,3], 2:[3,4], 3:[4], 4:[5,5]}, multiedges=True)
sage: p = GraphPaths(G, target=4)
sage: p == loads(dumps(p))
True

Functions: list

list( self)

sage: G = DiGraph({1:[2,2,3], 2:[3,4], 3:[4], 4:[5,5]}, multiedges=True)
sage: p = GraphPaths(G, target=4)
sage: p.list()
[[4],
 [2, 4],
 [1, 2, 4],
 [1, 2, 4],
 [3, 4],
 [1, 3, 4],
 [2, 3, 4],
 [1, 2, 3, 4],
 [1, 2, 3, 4]]

Special Functions: __init__, $\,$ __repr__

__repr__( self)

TESTS:

sage: G = DiGraph({1:[2,2,3], 2:[3,4], 3:[4], 4:[5,5]}, multiedges=True)
sage: p = GraphPaths(G, target=4)
sage: repr(p)
'Paths in Multi-digraph on 5 vertices ending at 4'

See About this document... for information on suggesting changes.