Paths in Directed Acyclic Graphs

sage.combinat.graph_path.GraphPaths(g, source=None, target=None)

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

EXAMPLES:

Sage

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

Python

>>> from sage.all import *
>>> G = DiGraph({Integer(1):[Integer(2),Integer(2),Integer(3)], Integer(2):[Integer(3),Integer(4)], Integer(3):[Integer(4)], Integer(4):[Integer(5),Integer(5)]}, multiedges=True)

Sage Live

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

sage: p = GraphPaths(G); p
Paths in Multi-digraph on 5 vertices
sage: p.cardinality()
37
sage: path = p.random_element()
sage: all(G.has_edge(*path[i:i+2]) for i in range(len(path) -1))
True

Python

>>> from sage.all import *
>>> p = GraphPaths(G); p
Paths in Multi-digraph on 5 vertices
>>> p.cardinality()
37
>>> path = p.random_element()
>>> all(G.has_edge(*path[i:i+Integer(2)]) for i in range(len(path) -Integer(1)))
True

Sage Live

p = GraphPaths(G); p
p.cardinality()
path = p.random_element()
all(G.has_edge(*path[i:i+2]) for i in range(len(path) -1))

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

Sage

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

Python

>>> from sage.all import *
>>> p = GraphPaths(G, source=Integer(3)); p
Paths in Multi-digraph on 5 vertices starting at 3
>>> p.list()
[[3], [3, 4], [3, 4, 5], [3, 4, 5]]

Sage Live

p = GraphPaths(G, source=3); p
p.list()

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

Sage

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

Python

>>> from sage.all import *
>>> p = GraphPaths(G, target=Integer(3)); p
Paths in Multi-digraph on 5 vertices ending at 3
>>> p.cardinality()
5
>>> p.list()
[[3], [1, 3], [2, 3], [1, 2, 3], [1, 2, 3]]

Sage Live

p = GraphPaths(G, target=3); p
p.cardinality()
p.list()

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

Sage

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.cardinality()
3
sage: p.list()
[[1, 2, 3], [1, 2, 3], [1, 3]]

Python

>>> from sage.all import *
>>> p = GraphPaths(G, source=Integer(1), target=Integer(3)); p
Paths in Multi-digraph on 5 vertices starting at 1 and ending at 3
>>> p.cardinality()
3
>>> p.list()
[[1, 2, 3], [1, 2, 3], [1, 3]]

Sage Live

p = GraphPaths(G, source=1, target=3); p
p.cardinality()
p.list()

Note that G must be a directed acyclic graph.

Sage

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

Python

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

Sage Live

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

class sage.combinat.graph_path.GraphPaths_all(g)

Bases: Parent, GraphPaths_common

EXAMPLES:

Sage

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

Python

>>> from sage.all import *
>>> G = DiGraph({Integer(1):[Integer(2),Integer(2),Integer(3)], Integer(2):[Integer(3),Integer(4)], Integer(3):[Integer(4)], Integer(4):[Integer(5),Integer(5)]}, multiedges=True)
>>> p = GraphPaths(G)
>>> p.cardinality()
37

Sage Live

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

list()

Return a list of the paths of self.

EXAMPLES:

Sage

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

Python

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

Sage Live

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

class sage.combinat.graph_path.GraphPaths_common

Bases: object

incoming_edges(v)

Return a list of v’s incoming edges.

EXAMPLES:

Sage

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

Python

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

Sage Live

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

incoming_paths(v)

Return a list of paths that end at v.

EXAMPLES:

Sage

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

Python

>>> from sage.all import *
>>> G = DiGraph({Integer(1):[Integer(2),Integer(2),Integer(3)], Integer(2):[Integer(3),Integer(4)], Integer(3):[Integer(4)], Integer(4):[Integer(5),Integer(5)]}, multiedges=True)
>>> gp = GraphPaths(G)
>>> gp.incoming_paths(Integer(2))
[[2], [1, 2], [1, 2]]

Sage Live

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

outgoing_edges(v)

Return a list of v’s outgoing edges.

EXAMPLES:

Sage

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

Python

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

Sage Live

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

outgoing_paths(v)

Return a list of the paths that start at v.

EXAMPLES:

Sage

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

Python

>>> from sage.all import *
>>> G = DiGraph({Integer(1):[Integer(2),Integer(2),Integer(3)], Integer(2):[Integer(3),Integer(4)], Integer(3):[Integer(4)], Integer(4):[Integer(5),Integer(5)]}, multiedges=True)
>>> gp = GraphPaths(G)
>>> gp.outgoing_paths(Integer(3))
[[3], [3, 4], [3, 4, 5], [3, 4, 5]]
>>> gp.outgoing_paths(Integer(2))
[[2],
 [2, 3],
 [2, 3, 4],
 [2, 3, 4, 5],
 [2, 3, 4, 5],
 [2, 4],
 [2, 4, 5],
 [2, 4, 5]]

Sage Live

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

paths()

Return a list of all the paths of self.

EXAMPLES:

Sage

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

Python

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

Sage Live

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

paths_from_source_to_target(source, target)

Return a list of paths from source to target.

EXAMPLES:

Sage

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

Python

>>> from sage.all import *
>>> G = DiGraph({Integer(1):[Integer(2),Integer(2),Integer(3)], Integer(2):[Integer(3),Integer(4)], Integer(3):[Integer(4)], Integer(4):[Integer(5),Integer(5)]}, multiedges=True)
>>> gp = GraphPaths(G)
>>> gp.paths_from_source_to_target(Integer(2),Integer(4))
[[2, 3, 4], [2, 4]]

Sage Live

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

class sage.combinat.graph_path.GraphPaths_s(g, source)

Bases: Parent, GraphPaths_common

list()

EXAMPLES:

Sage

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

Python

>>> from sage.all import *
>>> G = DiGraph({Integer(1):[Integer(2),Integer(2),Integer(3)], Integer(2):[Integer(3),Integer(4)], Integer(3):[Integer(4)], Integer(4):[Integer(5),Integer(5)]}, multiedges=True)
>>> p = GraphPaths(G, Integer(4))
>>> p.list()
[[4], [4, 5], [4, 5]]

Sage Live

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

class sage.combinat.graph_path.GraphPaths_st(g, source, target)

Bases: Parent, GraphPaths_common

EXAMPLES:

Sage

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

Python

>>> from sage.all import *
>>> G = DiGraph({Integer(1):[Integer(2),Integer(2),Integer(3)], Integer(2):[Integer(3),Integer(4)], Integer(3):[Integer(4)], Integer(4):[Integer(5),Integer(5)]}, multiedges=True)
>>> GraphPaths(G,Integer(1),Integer(2)).cardinality()
2
>>> GraphPaths(G,Integer(1),Integer(3)).cardinality()
3
>>> GraphPaths(G,Integer(1),Integer(4)).cardinality()
5
>>> GraphPaths(G,Integer(1),Integer(5)).cardinality()
10
>>> GraphPaths(G,Integer(2),Integer(3)).cardinality()
1
>>> GraphPaths(G,Integer(2),Integer(4)).cardinality()
2
>>> GraphPaths(G,Integer(2),Integer(5)).cardinality()
4
>>> GraphPaths(G,Integer(3),Integer(4)).cardinality()
1
>>> GraphPaths(G,Integer(3),Integer(5)).cardinality()
2
>>> GraphPaths(G,Integer(4),Integer(5)).cardinality()
2

Sage Live

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

list()

EXAMPLES:

Sage

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

Python

>>> from sage.all import *
>>> G = DiGraph({Integer(1):[Integer(2),Integer(2),Integer(3)], Integer(2):[Integer(3),Integer(4)], Integer(3):[Integer(4)], Integer(4):[Integer(5),Integer(5)]}, multiedges=True)
>>> p = GraphPaths(G,Integer(1),Integer(2))
>>> p.list()
[[1, 2], [1, 2]]

Sage Live

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

class sage.combinat.graph_path.GraphPaths_t(g, target)

Bases: Parent, GraphPaths_common

list()

EXAMPLES:

Sage

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

Python

>>> from sage.all import *
>>> G = DiGraph({Integer(1):[Integer(2),Integer(2),Integer(3)], Integer(2):[Integer(3),Integer(4)], Integer(3):[Integer(4)], Integer(4):[Integer(5),Integer(5)]}, multiedges=True)
>>> p = GraphPaths(G, target=Integer(4))
>>> 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]]

Sage Live

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

Make live