Paths in Directed Acyclic Graphs#
- sage.combinat.graph_path.GraphPaths(g, source=None, target=None)[source]#
Return the combinatorial class of paths in the directed acyclic graph g.
EXAMPLES:
sage: G = DiGraph({1:[2,2,3], 2:[3,4], 3:[4], 4:[5,5]}, multiedges=True)
>>> 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)
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.cardinality() 37 sage: path = p.random_element() sage: all(G.has_edge(*path[i:i+2]) for i in range(len(path) -1)) True
>>> 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
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]]
>>> 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]]
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.cardinality() 5 sage: p.list() [[3], [1, 3], [2, 3], [1, 2, 3], [1, 2, 3]]
>>> 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]]
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.cardinality() 3 sage: p.list() [[1, 2, 3], [1, 2, 3], [1, 3]]
>>> 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]]
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
>>> 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
- class sage.combinat.graph_path.GraphPaths_all(g)[source]#
Bases:
Parent
,GraphPaths_common
EXAMPLES:
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
>>> 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
- list()[source]#
Return a list of the paths of
self
.EXAMPLES:
sage: G = DiGraph({1:[2,2,3], 2:[3,4], 3:[4], 4:[5,5]}, multiedges=True) sage: len(GraphPaths(G).list()) 37
>>> 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
- class sage.combinat.graph_path.GraphPaths_common[source]#
Bases:
object
- incoming_edges(v)[source]#
Return a list of v’s incoming edges.
EXAMPLES:
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)]
>>> 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)]
- incoming_paths(v)[source]#
Return a list of paths that end at v.
EXAMPLES:
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]]
>>> 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]]
- outgoing_edges(v)[source]#
Return a list of v’s outgoing edges.
EXAMPLES:
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)]
>>> 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)]
- outgoing_paths(v)[source]#
Return a list of the paths that start at v.
EXAMPLES:
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]]
>>> 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]]
- paths()[source]#
Return a list of all the paths of
self
.EXAMPLES:
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
>>> 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
- paths_from_source_to_target(source, target)[source]#
Return a list of paths from source to target.
EXAMPLES:
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]]
>>> 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]]
- class sage.combinat.graph_path.GraphPaths_s(g, source)[source]#
Bases:
Parent
,GraphPaths_common
- list()[source]#
EXAMPLES:
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]]
>>> 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]]
- class sage.combinat.graph_path.GraphPaths_st(g, source, target)[source]#
Bases:
Parent
,GraphPaths_common
EXAMPLES:
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
>>> 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
- list()[source]#
EXAMPLES:
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]]
>>> 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]]
- class sage.combinat.graph_path.GraphPaths_t(g, target)[source]#
Bases:
Parent
,GraphPaths_common
- list()[source]#
EXAMPLES:
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]]
>>> 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]]