Path enumeration#

This module is meant for all functions related to path enumeration in graphs.

all_paths()

Return the list of all paths between a pair of vertices.

yen_k_shortest_simple_paths()

Return an iterator over the simple paths between a pair of vertices in increasing order of weights.

feng_k_shortest_simple_paths()

Return an iterator over the simple paths between a pair of vertices in increasing order of weights.

all_paths_iterator()

Return an iterator over the paths of self.

all_simple_paths()

Return a list of all the simple paths of self starting with one of the given vertices.

shortest_simple_paths()

Return an iterator over the simple paths between a pair of vertices.

Functions#

sage.graphs.path_enumeration.all_paths(G, start, end, use_multiedges=False, report_edges=False, labels=False)[source]#

Return the list of all paths between a pair of vertices.

If start is the same vertex as end, then [[start]] is returned – a list containing the 1-vertex, 0-edge path “start”.

If G has multiple edges, a path will be returned as many times as the product of the multiplicity of the edges along that path depending on the value of the flag use_multiedges.

INPUT:

  • start – a vertex of a graph, where to start

  • end – a vertex of a graph, where to end

  • use_multiedges – boolean (default: False); this parameter is used only if the graph has multiple edges.

    • If False, the graph is considered as simple and an edge label is arbitrarily selected for each edge as in sage.graphs.generic_graph.GenericGraph.to_simple() if report_edges is True

    • If True, a path will be reported as many times as the edges multiplicities along that path (when report_edges = False or labels = False), or with all possible combinations of edge labels (when report_edges = True and labels = True)

  • report_edges – boolean (default: False); whether to report paths as list of vertices (default) or list of edges, if False then labels parameter is ignored

  • labels – boolean (default: False); if False, each edge is simply a pair (u, v) of vertices. Otherwise a list of edges along with its edge labels are used to represent the path.

EXAMPLES:

sage: eg1 = Graph({0:[1, 2], 1:[4], 2:[3, 4], 4:[5], 5:[6]})
sage: eg1.all_paths(0, 6)
[[0, 1, 4, 5, 6], [0, 2, 4, 5, 6]]
sage: eg2 = graphs.PetersenGraph()
sage: sorted(eg2.all_paths(1, 4))
[[1, 0, 4],
 [1, 0, 5, 7, 2, 3, 4],
 [1, 0, 5, 7, 2, 3, 8, 6, 9, 4],
 [1, 0, 5, 7, 9, 4],
 [1, 0, 5, 7, 9, 6, 8, 3, 4],
 [1, 0, 5, 8, 3, 2, 7, 9, 4],
 [1, 0, 5, 8, 3, 4],
 [1, 0, 5, 8, 6, 9, 4],
 [1, 0, 5, 8, 6, 9, 7, 2, 3, 4],
 [1, 2, 3, 4],
 [1, 2, 3, 8, 5, 0, 4],
 [1, 2, 3, 8, 5, 7, 9, 4],
 [1, 2, 3, 8, 6, 9, 4],
 [1, 2, 3, 8, 6, 9, 7, 5, 0, 4],
 [1, 2, 7, 5, 0, 4],
 [1, 2, 7, 5, 8, 3, 4],
 [1, 2, 7, 5, 8, 6, 9, 4],
 [1, 2, 7, 9, 4],
 [1, 2, 7, 9, 6, 8, 3, 4],
 [1, 2, 7, 9, 6, 8, 5, 0, 4],
 [1, 6, 8, 3, 2, 7, 5, 0, 4],
 [1, 6, 8, 3, 2, 7, 9, 4],
 [1, 6, 8, 3, 4],
 [1, 6, 8, 5, 0, 4],
 [1, 6, 8, 5, 7, 2, 3, 4],
 [1, 6, 8, 5, 7, 9, 4],
 [1, 6, 9, 4],
 [1, 6, 9, 7, 2, 3, 4],
 [1, 6, 9, 7, 2, 3, 8, 5, 0, 4],
 [1, 6, 9, 7, 5, 0, 4],
 [1, 6, 9, 7, 5, 8, 3, 4]]
sage: dg = DiGraph({0:[1, 3], 1:[3], 2:[0, 3]})
sage: sorted(dg.all_paths(0, 3))
[[0, 1, 3], [0, 3]]
sage: ug = dg.to_undirected()
sage: sorted(ug.all_paths(0, 3))
[[0, 1, 3], [0, 2, 3], [0, 3]]

sage: g = Graph([(0, 1), (0, 1), (1, 2), (1, 2)], multiedges=True)
sage: g.all_paths(0, 2, use_multiedges=True)
[[0, 1, 2], [0, 1, 2], [0, 1, 2], [0, 1, 2]]

sage: dg = DiGraph({0:[1, 2, 1], 3:[0, 0]}, multiedges=True)
sage: dg.all_paths(3, 1, use_multiedges=True)
[[3, 0, 1], [3, 0, 1], [3, 0, 1], [3, 0, 1]]

sage: g = Graph([(0, 1, 'a'), (0, 1, 'b'), (1, 2, 'c'), (1, 2, 'd')], multiedges=True)
sage: g.all_paths(0, 2, use_multiedges=False)
[[0, 1, 2]]
sage: g.all_paths(0, 2, use_multiedges=True)
[[0, 1, 2], [0, 1, 2], [0, 1, 2], [0, 1, 2]]
sage: g.all_paths(0, 2, use_multiedges=True, report_edges=True)
[[(0, 1), (1, 2)], [(0, 1), (1, 2)], [(0, 1), (1, 2)], [(0, 1), (1, 2)]]
sage: g.all_paths(0, 2, use_multiedges=True, report_edges=True, labels=True)
[((0, 1, 'b'), (1, 2, 'd')),
 ((0, 1, 'b'), (1, 2, 'c')),
 ((0, 1, 'a'), (1, 2, 'd')),
 ((0, 1, 'a'), (1, 2, 'c'))]
sage: g.all_paths(0, 2, use_multiedges=False, report_edges=True, labels=True)
[((0, 1, 'b'), (1, 2, 'd'))]
sage: g.all_paths(0, 2, use_multiedges=False, report_edges=False, labels=True)
[[0, 1, 2]]
sage: g.all_paths(0, 2, use_multiedges=True, report_edges=False, labels=True)
[[0, 1, 2], [0, 1, 2], [0, 1, 2], [0, 1, 2]]

>>> from sage.all import *
>>> eg1 = Graph({Integer(0):[Integer(1), Integer(2)], Integer(1):[Integer(4)], Integer(2):[Integer(3), Integer(4)], Integer(4):[Integer(5)], Integer(5):[Integer(6)]})
>>> eg1.all_paths(Integer(0), Integer(6))
[[0, 1, 4, 5, 6], [0, 2, 4, 5, 6]]
>>> eg2 = graphs.PetersenGraph()
>>> sorted(eg2.all_paths(Integer(1), Integer(4)))
[[1, 0, 4],
 [1, 0, 5, 7, 2, 3, 4],
 [1, 0, 5, 7, 2, 3, 8, 6, 9, 4],
 [1, 0, 5, 7, 9, 4],
 [1, 0, 5, 7, 9, 6, 8, 3, 4],
 [1, 0, 5, 8, 3, 2, 7, 9, 4],
 [1, 0, 5, 8, 3, 4],
 [1, 0, 5, 8, 6, 9, 4],
 [1, 0, 5, 8, 6, 9, 7, 2, 3, 4],
 [1, 2, 3, 4],
 [1, 2, 3, 8, 5, 0, 4],
 [1, 2, 3, 8, 5, 7, 9, 4],
 [1, 2, 3, 8, 6, 9, 4],
 [1, 2, 3, 8, 6, 9, 7, 5, 0, 4],
 [1, 2, 7, 5, 0, 4],
 [1, 2, 7, 5, 8, 3, 4],
 [1, 2, 7, 5, 8, 6, 9, 4],
 [1, 2, 7, 9, 4],
 [1, 2, 7, 9, 6, 8, 3, 4],
 [1, 2, 7, 9, 6, 8, 5, 0, 4],
 [1, 6, 8, 3, 2, 7, 5, 0, 4],
 [1, 6, 8, 3, 2, 7, 9, 4],
 [1, 6, 8, 3, 4],
 [1, 6, 8, 5, 0, 4],
 [1, 6, 8, 5, 7, 2, 3, 4],
 [1, 6, 8, 5, 7, 9, 4],
 [1, 6, 9, 4],
 [1, 6, 9, 7, 2, 3, 4],
 [1, 6, 9, 7, 2, 3, 8, 5, 0, 4],
 [1, 6, 9, 7, 5, 0, 4],
 [1, 6, 9, 7, 5, 8, 3, 4]]
>>> dg = DiGraph({Integer(0):[Integer(1), Integer(3)], Integer(1):[Integer(3)], Integer(2):[Integer(0), Integer(3)]})
>>> sorted(dg.all_paths(Integer(0), Integer(3)))
[[0, 1, 3], [0, 3]]
>>> ug = dg.to_undirected()
>>> sorted(ug.all_paths(Integer(0), Integer(3)))
[[0, 1, 3], [0, 2, 3], [0, 3]]

>>> g = Graph([(Integer(0), Integer(1)), (Integer(0), Integer(1)), (Integer(1), Integer(2)), (Integer(1), Integer(2))], multiedges=True)
>>> g.all_paths(Integer(0), Integer(2), use_multiedges=True)
[[0, 1, 2], [0, 1, 2], [0, 1, 2], [0, 1, 2]]

>>> dg = DiGraph({Integer(0):[Integer(1), Integer(2), Integer(1)], Integer(3):[Integer(0), Integer(0)]}, multiedges=True)
>>> dg.all_paths(Integer(3), Integer(1), use_multiedges=True)
[[3, 0, 1], [3, 0, 1], [3, 0, 1], [3, 0, 1]]

>>> g = Graph([(Integer(0), Integer(1), 'a'), (Integer(0), Integer(1), 'b'), (Integer(1), Integer(2), 'c'), (Integer(1), Integer(2), 'd')], multiedges=True)
>>> g.all_paths(Integer(0), Integer(2), use_multiedges=False)
[[0, 1, 2]]
>>> g.all_paths(Integer(0), Integer(2), use_multiedges=True)
[[0, 1, 2], [0, 1, 2], [0, 1, 2], [0, 1, 2]]
>>> g.all_paths(Integer(0), Integer(2), use_multiedges=True, report_edges=True)
[[(0, 1), (1, 2)], [(0, 1), (1, 2)], [(0, 1), (1, 2)], [(0, 1), (1, 2)]]
>>> g.all_paths(Integer(0), Integer(2), use_multiedges=True, report_edges=True, labels=True)
[((0, 1, 'b'), (1, 2, 'd')),
 ((0, 1, 'b'), (1, 2, 'c')),
 ((0, 1, 'a'), (1, 2, 'd')),
 ((0, 1, 'a'), (1, 2, 'c'))]
>>> g.all_paths(Integer(0), Integer(2), use_multiedges=False, report_edges=True, labels=True)
[((0, 1, 'b'), (1, 2, 'd'))]
>>> g.all_paths(Integer(0), Integer(2), use_multiedges=False, report_edges=False, labels=True)
[[0, 1, 2]]
>>> g.all_paths(Integer(0), Integer(2), use_multiedges=True, report_edges=False, labels=True)
[[0, 1, 2], [0, 1, 2], [0, 1, 2], [0, 1, 2]]
sage.graphs.path_enumeration.all_paths_iterator(self, starting_vertices=None, ending_vertices=None, simple=False, max_length=None, trivial=False, use_multiedges=False, report_edges=False, labels=False)[source]#

Return an iterator over the paths of self.

The paths are enumerated in increasing length order.

INPUT:

  • starting_vertices – iterable (default: None); vertices from which the paths must start. If None, then all vertices of the graph can be starting points.

  • ending_vertices – iterable (default: None); allowed ending vertices of the paths. If None, then all vertices are allowed.

  • simple – boolean (default: False); if set to True, then only simple paths are considered. Simple paths are paths in which no two arcs share a head or share a tail, i.e. every vertex in the path is entered at most once and exited at most once.

  • max_length – non negative integer (default: None); the maximum length of the enumerated paths. If set to None, then all lengths are allowed.

  • trivial – boolean (default: False); if set to True, then the empty paths are also enumerated.

  • use_multiedges – boolean (default: False); this parameter is used only if the graph has multiple edges.

    • If False, the graph is considered as simple and an edge label is arbitrarily selected for each edge as in sage.graphs.generic_graph.GenericGraph.to_simple() if report_edges is True

    • If True, a path will be reported as many times as the edges multiplicities along that path (when report_edges = False or labels = False), or with all possible combinations of edge labels (when report_edges = True and labels = True)

  • report_edges – boolean (default: False); whether to report paths as list of vertices (default) or list of edges, if False then labels parameter is ignored

  • labels – boolean (default: False); if False, each edge is simply a pair (u, v) of vertices. Otherwise a list of edges along with its edge labels are used to represent the path.

OUTPUT:

iterator

AUTHOR:

Alexandre Blondin Masse

EXAMPLES:

sage: G = graphs.CompleteGraph(4)
sage: list(G.all_paths_iterator(starting_vertices=[1], ending_vertices=[3], simple=True))
[[1, 3], [1, 0, 3], [1, 2, 3], [1, 0, 2, 3], [1, 2, 0, 3]]
sage: list(G.shortest_simple_paths(1, 3))
[[1, 3], [1, 0, 3], [1, 2, 3], [1, 2, 0, 3], [1, 0, 2, 3]]
sage: pi = G.all_paths_iterator(starting_vertices=[1], ending_vertices=[3])
sage: for _ in range(6):
....:     print(next(pi))
[1, 3]
[1, 0, 3]
[1, 2, 3]
[1, 0, 1, 3]
[1, 0, 2, 3]
[1, 2, 0, 3]

sage: g = DiGraph({'a': ['a', 'b'], 'b': ['c'], 'c': ['d'], 'd': ['c']}, loops=True)
sage: pi = g.all_paths_iterator(starting_vertices=['a'], ending_vertices=['d'], report_edges=True, simple=True)
sage: list(pi)
[[('a', 'b'), ('b', 'c'), ('c', 'd')]]

sage: g = DiGraph([(0, 1, 'a'), (0, 1, 'b'), (1, 2,'c'), (1, 2,'d')], multiedges=True)
sage: pi =  g.all_paths_iterator(starting_vertices=[0], use_multiedges=True)
sage: for _ in range(6):
....:     print(next(pi))
[0, 1]
[0, 1]
[0, 1, 2]
[0, 1, 2]
[0, 1, 2]
[0, 1, 2]
sage: pi =  g.all_paths_iterator(starting_vertices=[0], use_multiedges=True, report_edges=True, labels=True)
sage: for _ in range(6):
....:     print(next(pi))
[(0, 1, 'b')]
[(0, 1, 'a')]
[(0, 1, 'b'), (1, 2, 'd')]
[(0, 1, 'b'), (1, 2, 'c')]
[(0, 1, 'a'), (1, 2, 'd')]
[(0, 1, 'a'), (1, 2, 'c')]
sage: list(g.all_paths_iterator(starting_vertices=[0, 1], ending_vertices=[2], use_multiedges=False, report_edges=True, labels=True, simple=True))
[[(1, 2, 'd')], [(0, 1, 'b'), (1, 2, 'd')]]
sage: list(g.all_paths_iterator(starting_vertices=[0, 1], ending_vertices=[2], use_multiedges=False, report_edges=False, labels=True))
[[1, 2], [0, 1, 2]]
sage: list(g.all_paths_iterator(use_multiedges=True, report_edges=False, labels=True, max_length=1))
[[1, 2], [1, 2], [0, 1], [0, 1]]
sage: list(g.all_paths_iterator(use_multiedges=True, report_edges=True, labels=True, max_length=1))
[[(1, 2, 'd')], [(1, 2, 'c')], [(0, 1, 'b')], [(0, 1, 'a')]]

sage: g = DiGraph({'a': ['a', 'b'], 'b': ['c'], 'c': ['d'], 'd': ['c']}, loops=True)
sage: pi = g.all_paths_iterator()
sage: [len(next(pi)) - 1 for _ in range(7)]
[1, 1, 1, 1, 1, 2, 2]

>>> from sage.all import *
>>> G = graphs.CompleteGraph(Integer(4))
>>> list(G.all_paths_iterator(starting_vertices=[Integer(1)], ending_vertices=[Integer(3)], simple=True))
[[1, 3], [1, 0, 3], [1, 2, 3], [1, 0, 2, 3], [1, 2, 0, 3]]
>>> list(G.shortest_simple_paths(Integer(1), Integer(3)))
[[1, 3], [1, 0, 3], [1, 2, 3], [1, 2, 0, 3], [1, 0, 2, 3]]
>>> pi = G.all_paths_iterator(starting_vertices=[Integer(1)], ending_vertices=[Integer(3)])
>>> for _ in range(Integer(6)):
...     print(next(pi))
[1, 3]
[1, 0, 3]
[1, 2, 3]
[1, 0, 1, 3]
[1, 0, 2, 3]
[1, 2, 0, 3]

>>> g = DiGraph({'a': ['a', 'b'], 'b': ['c'], 'c': ['d'], 'd': ['c']}, loops=True)
>>> pi = g.all_paths_iterator(starting_vertices=['a'], ending_vertices=['d'], report_edges=True, simple=True)
>>> list(pi)
[[('a', 'b'), ('b', 'c'), ('c', 'd')]]

>>> g = DiGraph([(Integer(0), Integer(1), 'a'), (Integer(0), Integer(1), 'b'), (Integer(1), Integer(2),'c'), (Integer(1), Integer(2),'d')], multiedges=True)
>>> pi =  g.all_paths_iterator(starting_vertices=[Integer(0)], use_multiedges=True)
>>> for _ in range(Integer(6)):
...     print(next(pi))
[0, 1]
[0, 1]
[0, 1, 2]
[0, 1, 2]
[0, 1, 2]
[0, 1, 2]
>>> pi =  g.all_paths_iterator(starting_vertices=[Integer(0)], use_multiedges=True, report_edges=True, labels=True)
>>> for _ in range(Integer(6)):
...     print(next(pi))
[(0, 1, 'b')]
[(0, 1, 'a')]
[(0, 1, 'b'), (1, 2, 'd')]
[(0, 1, 'b'), (1, 2, 'c')]
[(0, 1, 'a'), (1, 2, 'd')]
[(0, 1, 'a'), (1, 2, 'c')]
>>> list(g.all_paths_iterator(starting_vertices=[Integer(0), Integer(1)], ending_vertices=[Integer(2)], use_multiedges=False, report_edges=True, labels=True, simple=True))
[[(1, 2, 'd')], [(0, 1, 'b'), (1, 2, 'd')]]
>>> list(g.all_paths_iterator(starting_vertices=[Integer(0), Integer(1)], ending_vertices=[Integer(2)], use_multiedges=False, report_edges=False, labels=True))
[[1, 2], [0, 1, 2]]
>>> list(g.all_paths_iterator(use_multiedges=True, report_edges=False, labels=True, max_length=Integer(1)))
[[1, 2], [1, 2], [0, 1], [0, 1]]
>>> list(g.all_paths_iterator(use_multiedges=True, report_edges=True, labels=True, max_length=Integer(1)))
[[(1, 2, 'd')], [(1, 2, 'c')], [(0, 1, 'b')], [(0, 1, 'a')]]

>>> g = DiGraph({'a': ['a', 'b'], 'b': ['c'], 'c': ['d'], 'd': ['c']}, loops=True)
>>> pi = g.all_paths_iterator()
>>> [len(next(pi)) - Integer(1) for _ in range(Integer(7))]
[1, 1, 1, 1, 1, 2, 2]

It is possible to precise the allowed starting and/or ending vertices:

sage: pi = g.all_paths_iterator(starting_vertices=['a'])
sage: [len(next(pi)) - 1 for _ in range(5)]
[1, 1, 2, 2, 2]
sage: pi = g.all_paths_iterator(starting_vertices=['a'], ending_vertices=['b'])
sage: for _ in range(5):
....:     print(next(pi))
['a', 'b']
['a', 'a', 'b']
['a', 'a', 'a', 'b']
['a', 'a', 'a', 'a', 'b']
['a', 'a', 'a', 'a', 'a', 'b']

>>> from sage.all import *
>>> pi = g.all_paths_iterator(starting_vertices=['a'])
>>> [len(next(pi)) - Integer(1) for _ in range(Integer(5))]
[1, 1, 2, 2, 2]
>>> pi = g.all_paths_iterator(starting_vertices=['a'], ending_vertices=['b'])
>>> for _ in range(Integer(5)):
...     print(next(pi))
['a', 'b']
['a', 'a', 'b']
['a', 'a', 'a', 'b']
['a', 'a', 'a', 'a', 'b']
['a', 'a', 'a', 'a', 'a', 'b']

One may prefer to enumerate only simple paths (see all_simple_paths()):

sage: pi = g.all_paths_iterator(simple=True)
sage: sorted(list(pi), key=lambda x:(len(x), x))
[['a', 'a'], ['a', 'b'], ['b', 'c'], ['c', 'd'], ['d', 'c'],
    ['a', 'b', 'c'], ['b', 'c', 'd'], ['c', 'd', 'c'], ['d', 'c', 'd'],
    ['a', 'b', 'c', 'd']]
sage: pi = g.all_paths_iterator(simple=True)
sage: [len(p) - 1 for p in pi]
[1, 1, 1, 1, 1, 2, 2, 2, 2, 3]

>>> from sage.all import *
>>> pi = g.all_paths_iterator(simple=True)
>>> sorted(list(pi), key=lambda x:(len(x), x))
[['a', 'a'], ['a', 'b'], ['b', 'c'], ['c', 'd'], ['d', 'c'],
    ['a', 'b', 'c'], ['b', 'c', 'd'], ['c', 'd', 'c'], ['d', 'c', 'd'],
    ['a', 'b', 'c', 'd']]
>>> pi = g.all_paths_iterator(simple=True)
>>> [len(p) - Integer(1) for p in pi]
[1, 1, 1, 1, 1, 2, 2, 2, 2, 3]

Or simply bound the length of the enumerated paths:

sage: pi = g.all_paths_iterator(starting_vertices=['a'], ending_vertices=['b', 'c'], max_length=6)
sage: sorted(list(pi), key=lambda x:(len(x), x))
[['a', 'b'], ['a', 'a', 'b'], ['a', 'b', 'c'], ['a', 'a', 'a', 'b'],
    ['a', 'a', 'b', 'c'], ['a', 'a', 'a', 'a', 'b'],
    ['a', 'a', 'a', 'b', 'c'], ['a', 'b', 'c', 'd', 'c'],
    ['a', 'a', 'a', 'a', 'a', 'b'], ['a', 'a', 'a', 'a', 'b', 'c'],
    ['a', 'a', 'b', 'c', 'd', 'c'],
    ['a', 'a', 'a', 'a', 'a', 'a', 'b'],
    ['a', 'a', 'a', 'a', 'a', 'b', 'c'],
    ['a', 'a', 'a', 'b', 'c', 'd', 'c'],
    ['a', 'b', 'c', 'd', 'c', 'd', 'c']]
sage: pi = g.all_paths_iterator(starting_vertices=['a'], ending_vertices=['b', 'c'], max_length=6)
sage: [len(p) - 1 for p in pi]
[1, 2, 2, 3, 3, 4, 4, 4, 5, 5, 5, 6, 6, 6, 6]

>>> from sage.all import *
>>> pi = g.all_paths_iterator(starting_vertices=['a'], ending_vertices=['b', 'c'], max_length=Integer(6))
>>> sorted(list(pi), key=lambda x:(len(x), x))
[['a', 'b'], ['a', 'a', 'b'], ['a', 'b', 'c'], ['a', 'a', 'a', 'b'],
    ['a', 'a', 'b', 'c'], ['a', 'a', 'a', 'a', 'b'],
    ['a', 'a', 'a', 'b', 'c'], ['a', 'b', 'c', 'd', 'c'],
    ['a', 'a', 'a', 'a', 'a', 'b'], ['a', 'a', 'a', 'a', 'b', 'c'],
    ['a', 'a', 'b', 'c', 'd', 'c'],
    ['a', 'a', 'a', 'a', 'a', 'a', 'b'],
    ['a', 'a', 'a', 'a', 'a', 'b', 'c'],
    ['a', 'a', 'a', 'b', 'c', 'd', 'c'],
    ['a', 'b', 'c', 'd', 'c', 'd', 'c']]
>>> pi = g.all_paths_iterator(starting_vertices=['a'], ending_vertices=['b', 'c'], max_length=Integer(6))
>>> [len(p) - Integer(1) for p in pi]
[1, 2, 2, 3, 3, 4, 4, 4, 5, 5, 5, 6, 6, 6, 6]

By default, empty paths are not enumerated, but it may be parametrized:

sage: pi = g.all_paths_iterator(simple=True, trivial=True)
sage: sorted(list(pi), key=lambda x:(len(x), x))
[['a'], ['b'], ['c'], ['d'], ['a', 'a'], ['a', 'b'], ['b', 'c'],
    ['c', 'd'], ['d', 'c'], ['a', 'b', 'c'], ['b', 'c', 'd'],
    ['c', 'd', 'c'], ['d', 'c', 'd'], ['a', 'b', 'c', 'd']]
sage: pi = g.all_paths_iterator(simple=True, trivial=True)
sage: [len(p) - 1 for p in pi]
[0, 0, 0, 0, 1, 1, 1, 1, 1, 2, 2, 2, 2, 3]
sage: pi = g.all_paths_iterator(simple=True, trivial=False)
sage: sorted(list(pi), key=lambda x:(len(x), x))
[['a', 'a'], ['a', 'b'], ['b', 'c'], ['c', 'd'], ['d', 'c'],
    ['a', 'b', 'c'], ['b', 'c', 'd'], ['c', 'd', 'c'], ['d', 'c', 'd'],
    ['a', 'b', 'c', 'd']]
sage: pi = g.all_paths_iterator(simple=True, trivial=False)
sage: [len(p) - 1 for p in pi]
[1, 1, 1, 1, 1, 2, 2, 2, 2, 3]

>>> from sage.all import *
>>> pi = g.all_paths_iterator(simple=True, trivial=True)
>>> sorted(list(pi), key=lambda x:(len(x), x))
[['a'], ['b'], ['c'], ['d'], ['a', 'a'], ['a', 'b'], ['b', 'c'],
    ['c', 'd'], ['d', 'c'], ['a', 'b', 'c'], ['b', 'c', 'd'],
    ['c', 'd', 'c'], ['d', 'c', 'd'], ['a', 'b', 'c', 'd']]
>>> pi = g.all_paths_iterator(simple=True, trivial=True)
>>> [len(p) - Integer(1) for p in pi]
[0, 0, 0, 0, 1, 1, 1, 1, 1, 2, 2, 2, 2, 3]
>>> pi = g.all_paths_iterator(simple=True, trivial=False)
>>> sorted(list(pi), key=lambda x:(len(x), x))
[['a', 'a'], ['a', 'b'], ['b', 'c'], ['c', 'd'], ['d', 'c'],
    ['a', 'b', 'c'], ['b', 'c', 'd'], ['c', 'd', 'c'], ['d', 'c', 'd'],
    ['a', 'b', 'c', 'd']]
>>> pi = g.all_paths_iterator(simple=True, trivial=False)
>>> [len(p) - Integer(1) for p in pi]
[1, 1, 1, 1, 1, 2, 2, 2, 2, 3]
sage.graphs.path_enumeration.all_simple_paths(self, starting_vertices=None, ending_vertices=None, max_length=None, trivial=False, use_multiedges=False, report_edges=False, labels=False)[source]#

Return a list of all the simple paths of self starting with one of the given vertices.

Simple paths are paths in which no two arcs share a head or share a tail, i.e. every vertex in the path is entered at most once and exited at most once.

INPUT:

  • starting_vertices – list (default: None); vertices from which the paths must start. If None, then all vertices of the graph can be starting points.

  • ending_vertices – iterable (default: None); allowed ending vertices of the paths. If None, then all vertices are allowed.

  • max_length – non negative integer (default: None); the maximum length of the enumerated paths. If set to None, then all lengths are allowed.

  • trivial – boolean (default: False); if set to True, then the empty paths are also enumerated.

  • use_multiedges – boolean (default: False); this parameter is used only if the graph has multiple edges.

    • If False, the graph is considered as simple and an edge label is arbitrarily selected for each edge as in sage.graphs.generic_graph.GenericGraph.to_simple() if report_edges is True

    • If True, a path will be reported as many times as the edges multiplicities along that path (when report_edges = False or labels = False), or with all possible combinations of edge labels (when report_edges = True and labels = True)

  • report_edges – boolean (default: False); whether to report paths as list of vertices (default) or list of edges, if False then labels parameter is ignored

  • labels – boolean (default: False); if False, each edge is simply a pair (u, v) of vertices. Otherwise a list of edges along with its edge labels are used to represent the path.

OUTPUT:

list

Note

Although the number of simple paths of a finite graph is always finite, computing all its paths may take a very long time.

EXAMPLES:

sage: G = graphs.CompleteGraph(4)
sage: G.all_simple_paths([1], [3])
[[1, 3], [1, 0, 3], [1, 2, 3], [1, 0, 2, 3], [1, 2, 0, 3]]
sage: list(G.shortest_simple_paths(1, 3))
[[1, 3], [1, 0, 3], [1, 2, 3], [1, 2, 0, 3], [1, 0, 2, 3]]
sage: G.all_simple_paths([0, 1], [2, 3])
[[1, 2],
 [1, 3],
 [0, 2],
 [0, 3],
 [0, 1, 2],
 [0, 1, 3],
 [0, 2, 3],
 [0, 3, 2],
 [1, 0, 2],
 [1, 0, 3],
 [1, 2, 3],
 [1, 3, 2],
 [1, 0, 2, 3],
 [1, 0, 3, 2],
 [1, 2, 0, 3],
 [1, 3, 0, 2],
 [0, 1, 2, 3],
 [0, 1, 3, 2],
 [0, 2, 1, 3],
 [0, 3, 1, 2]]

sage: g = DiGraph({0: [0, 1], 1: [2], 2: [3], 3: [2]}, loops=True)
sage: g.all_simple_paths()
[[3, 2],
 [2, 3],
 [1, 2],
 [0, 0],
 [0, 1],
 [0, 1, 2],
 [1, 2, 3],
 [2, 3, 2],
 [3, 2, 3],
 [0, 1, 2, 3]]

sage: g = DiGraph([(0, 1, 'a'), (0, 1, 'b'), (1, 2,'c'), (1, 2,'d')], multiedges=True)
sage: g.all_simple_paths(starting_vertices=[0], ending_vertices=[2], use_multiedges=False)
[[0, 1, 2]]
sage: g.all_simple_paths(starting_vertices=[0], ending_vertices=[2], use_multiedges=True)
[[0, 1, 2], [0, 1, 2], [0, 1, 2], [0, 1, 2]]
sage: g.all_simple_paths(starting_vertices=[0], ending_vertices=[2], use_multiedges=True, report_edges=True)
[[(0, 1), (1, 2)], [(0, 1), (1, 2)], [(0, 1), (1, 2)], [(0, 1), (1, 2)]]
sage: g.all_simple_paths(starting_vertices=[0], ending_vertices=[2], use_multiedges=True, report_edges=True, labels=True)
[[(0, 1, 'b'), (1, 2, 'd')],
 [(0, 1, 'b'), (1, 2, 'c')],
 [(0, 1, 'a'), (1, 2, 'd')],
 [(0, 1, 'a'), (1, 2, 'c')]]
sage: g.all_simple_paths(starting_vertices=[0, 1], ending_vertices=[2], use_multiedges=False, report_edges=True, labels=True)
[[(1, 2, 'd')], [(0, 1, 'b'), (1, 2, 'd')]]
sage: g.all_simple_paths(starting_vertices=[0, 1], ending_vertices=[2], use_multiedges=False, report_edges=False, labels=True)
[[1, 2], [0, 1, 2]]
sage: g.all_simple_paths(use_multiedges=True, report_edges=False, labels=True)
[[1, 2], [1, 2], [0, 1], [0, 1], [0, 1, 2], [0, 1, 2], [0, 1, 2], [0, 1, 2]]
sage: g.all_simple_paths(starting_vertices=[0, 1], ending_vertices=[2], use_multiedges=False, report_edges=True, labels=True, trivial=True)
[[(1, 2, 'd')], [(0, 1, 'b'), (1, 2, 'd')]]

>>> from sage.all import *
>>> G = graphs.CompleteGraph(Integer(4))
>>> G.all_simple_paths([Integer(1)], [Integer(3)])
[[1, 3], [1, 0, 3], [1, 2, 3], [1, 0, 2, 3], [1, 2, 0, 3]]
>>> list(G.shortest_simple_paths(Integer(1), Integer(3)))
[[1, 3], [1, 0, 3], [1, 2, 3], [1, 2, 0, 3], [1, 0, 2, 3]]
>>> G.all_simple_paths([Integer(0), Integer(1)], [Integer(2), Integer(3)])
[[1, 2],
 [1, 3],
 [0, 2],
 [0, 3],
 [0, 1, 2],
 [0, 1, 3],
 [0, 2, 3],
 [0, 3, 2],
 [1, 0, 2],
 [1, 0, 3],
 [1, 2, 3],
 [1, 3, 2],
 [1, 0, 2, 3],
 [1, 0, 3, 2],
 [1, 2, 0, 3],
 [1, 3, 0, 2],
 [0, 1, 2, 3],
 [0, 1, 3, 2],
 [0, 2, 1, 3],
 [0, 3, 1, 2]]

>>> g = DiGraph({Integer(0): [Integer(0), Integer(1)], Integer(1): [Integer(2)], Integer(2): [Integer(3)], Integer(3): [Integer(2)]}, loops=True)
>>> g.all_simple_paths()
[[3, 2],
 [2, 3],
 [1, 2],
 [0, 0],
 [0, 1],
 [0, 1, 2],
 [1, 2, 3],
 [2, 3, 2],
 [3, 2, 3],
 [0, 1, 2, 3]]

>>> g = DiGraph([(Integer(0), Integer(1), 'a'), (Integer(0), Integer(1), 'b'), (Integer(1), Integer(2),'c'), (Integer(1), Integer(2),'d')], multiedges=True)
>>> g.all_simple_paths(starting_vertices=[Integer(0)], ending_vertices=[Integer(2)], use_multiedges=False)
[[0, 1, 2]]
>>> g.all_simple_paths(starting_vertices=[Integer(0)], ending_vertices=[Integer(2)], use_multiedges=True)
[[0, 1, 2], [0, 1, 2], [0, 1, 2], [0, 1, 2]]
>>> g.all_simple_paths(starting_vertices=[Integer(0)], ending_vertices=[Integer(2)], use_multiedges=True, report_edges=True)
[[(0, 1), (1, 2)], [(0, 1), (1, 2)], [(0, 1), (1, 2)], [(0, 1), (1, 2)]]
>>> g.all_simple_paths(starting_vertices=[Integer(0)], ending_vertices=[Integer(2)], use_multiedges=True, report_edges=True, labels=True)
[[(0, 1, 'b'), (1, 2, 'd')],
 [(0, 1, 'b'), (1, 2, 'c')],
 [(0, 1, 'a'), (1, 2, 'd')],
 [(0, 1, 'a'), (1, 2, 'c')]]
>>> g.all_simple_paths(starting_vertices=[Integer(0), Integer(1)], ending_vertices=[Integer(2)], use_multiedges=False, report_edges=True, labels=True)
[[(1, 2, 'd')], [(0, 1, 'b'), (1, 2, 'd')]]
>>> g.all_simple_paths(starting_vertices=[Integer(0), Integer(1)], ending_vertices=[Integer(2)], use_multiedges=False, report_edges=False, labels=True)
[[1, 2], [0, 1, 2]]
>>> g.all_simple_paths(use_multiedges=True, report_edges=False, labels=True)
[[1, 2], [1, 2], [0, 1], [0, 1], [0, 1, 2], [0, 1, 2], [0, 1, 2], [0, 1, 2]]
>>> g.all_simple_paths(starting_vertices=[Integer(0), Integer(1)], ending_vertices=[Integer(2)], use_multiedges=False, report_edges=True, labels=True, trivial=True)
[[(1, 2, 'd')], [(0, 1, 'b'), (1, 2, 'd')]]

One may compute all paths having specific starting and/or ending vertices:

sage: g = DiGraph({'a': ['a', 'b'], 'b': ['c'], 'c': ['d'], 'd': ['c']}, loops=True)
sage: g.all_simple_paths(starting_vertices=['a'])
[['a', 'a'], ['a', 'b'], ['a', 'b', 'c'], ['a', 'b', 'c', 'd']]
sage: g.all_simple_paths(starting_vertices=['a'], ending_vertices=['c'])
[['a', 'b', 'c']]
sage: g.all_simple_paths(starting_vertices=['a'], ending_vertices=['b', 'c'])
[['a', 'b'], ['a', 'b', 'c']]

>>> from sage.all import *
>>> g = DiGraph({'a': ['a', 'b'], 'b': ['c'], 'c': ['d'], 'd': ['c']}, loops=True)
>>> g.all_simple_paths(starting_vertices=['a'])
[['a', 'a'], ['a', 'b'], ['a', 'b', 'c'], ['a', 'b', 'c', 'd']]
>>> g.all_simple_paths(starting_vertices=['a'], ending_vertices=['c'])
[['a', 'b', 'c']]
>>> g.all_simple_paths(starting_vertices=['a'], ending_vertices=['b', 'c'])
[['a', 'b'], ['a', 'b', 'c']]

It is also possible to bound the length of the paths:

sage: g = DiGraph({0: [0, 1], 1: [2], 2: [3], 3: [2]}, loops=True)
sage: g.all_simple_paths(max_length=2)
[[3, 2],
 [2, 3],
 [1, 2],
 [0, 0],
 [0, 1],
 [0, 1, 2],
 [1, 2, 3],
 [2, 3, 2],
 [3, 2, 3]]

>>> from sage.all import *
>>> g = DiGraph({Integer(0): [Integer(0), Integer(1)], Integer(1): [Integer(2)], Integer(2): [Integer(3)], Integer(3): [Integer(2)]}, loops=True)
>>> g.all_simple_paths(max_length=Integer(2))
[[3, 2],
 [2, 3],
 [1, 2],
 [0, 0],
 [0, 1],
 [0, 1, 2],
 [1, 2, 3],
 [2, 3, 2],
 [3, 2, 3]]

By default, empty paths are not enumerated, but this can be parametrized:

sage: g = DiGraph({'a': ['a', 'b'], 'b': ['c'], 'c': ['d'], 'd': ['c']}, loops=True)
sage: g.all_simple_paths(starting_vertices=['a'], trivial=True)
[['a'], ['a', 'a'], ['a', 'b'], ['a', 'b', 'c'],
 ['a', 'b', 'c', 'd']]
sage: g.all_simple_paths(starting_vertices=['a'], trivial=False)
[['a', 'a'], ['a', 'b'], ['a', 'b', 'c'], ['a', 'b', 'c', 'd']]

>>> from sage.all import *
>>> g = DiGraph({'a': ['a', 'b'], 'b': ['c'], 'c': ['d'], 'd': ['c']}, loops=True)
>>> g.all_simple_paths(starting_vertices=['a'], trivial=True)
[['a'], ['a', 'a'], ['a', 'b'], ['a', 'b', 'c'],
 ['a', 'b', 'c', 'd']]
>>> g.all_simple_paths(starting_vertices=['a'], trivial=False)
[['a', 'a'], ['a', 'b'], ['a', 'b', 'c'], ['a', 'b', 'c', 'd']]
sage.graphs.path_enumeration.feng_k_shortest_simple_paths(self, source, target, weight_function=None, by_weight=False, check_weight=True, report_edges=False, labels=False, report_weight=False)[source]#

Return an iterator over the simple paths between a pair of vertices in increasing order of weights.

Works only for directed graphs.

For unweighted graphs, paths are returned in order of increasing number of edges.

In case of weighted graphs, negative weights are not allowed.

If source is the same vertex as target, then [[source]] is returned – a list containing the 1-vertex, 0-edge path source.

The loops and the multiedges if present in the given graph are ignored and only minimum of the edge labels is kept in case of multiedges.

INPUT:

  • source – a vertex of the graph, where to start

  • target – a vertex of the graph, where to end

  • weight_function – function (default: None); a function that takes as input an edge (u, v, l) and outputs its weight. If not None, by_weight is automatically set to True. If None and by_weight is True, we use the edge label l as a weight.

  • by_weight – boolean (default: False); if True, the edges in the graph are weighted, otherwise all edges have weight 1

  • check_weight – boolean (default: True); whether to check that the weight_function outputs a number for each edge

  • report_edges – boolean (default: False); whether to report paths as list of vertices (default) or list of edges, if False then labels parameter is ignored

  • labels – boolean (default: False); if False, each edge is simply a pair (u, v) of vertices. Otherwise a list of edges along with its edge labels are used to represent the path.

  • report_weight – boolean (default: False); if False, just the path between source and target is returned. Otherwise a tuple of path length and path is returned.

ALGORITHM:

This algorithm can be divided into two parts. Firstly, it determines the shortest path from source to target. Then, it determines all the other \(k\)-shortest paths. This algorithm finds the deviations of previous shortest paths to determine the next shortest paths. This algorithm finds the candidate paths more efficiently using a node classification technique. At first the candidate path is separated by its deviation node as prefix and suffix. Then the algorithm classify the nodes as red, yellow and green. A node on the prefix is assigned a red color, a node that can reach t (the destination node) through a shortest path without visiting a red node is assigned a green color, and all other nodes are assigned a yellow color. When searching for the suffix of a candidate path, all green nodes are bypassed, and Dijkstra’s algorithm is applied to find an all-yellow-node subpath. Since on average the number of yellow nodes is much smaller than n, this algorithm has a much lower average-case running time.

Time complexity is \(O(kn(m+n\log{n}))\) where \(n\) is the number of vertices and \(m\) is the number of edges and \(k\) is the number of shortest paths needed to find. Its average running time is much smaller as compared to \(Yen's\) algorithm.

See [Feng2014] for more details on this algorithm.

EXAMPLES:

sage: from sage.graphs.path_enumeration import feng_k_shortest_simple_paths
sage: g = DiGraph([(1, 2, 20), (1, 3, 10), (1, 4, 30), (2, 5, 20), (3, 5, 10), (4, 5, 30)])
sage: list(feng_k_shortest_simple_paths(g, 1, 5, by_weight=True))
[[1, 3, 5], [1, 2, 5], [1, 4, 5]]
sage: list(feng_k_shortest_simple_paths(g, 1, 5))
[[1, 4, 5], [1, 3, 5], [1, 2, 5]]
sage: list(feng_k_shortest_simple_paths(g, 1, 1))
[[1]]
sage: list(feng_k_shortest_simple_paths(g, 1, 5, report_edges=True, labels=True))
[[(1, 4, 30), (4, 5, 30)], [(1, 3, 10), (3, 5, 10)], [(1, 2, 20), (2, 5, 20)]]
sage: list(feng_k_shortest_simple_paths(g, 1, 5, report_edges=True, labels=True, by_weight=True))
[[(1, 3, 10), (3, 5, 10)], [(1, 2, 20), (2, 5, 20)], [(1, 4, 30), (4, 5, 30)]]
sage: list(feng_k_shortest_simple_paths(g, 1, 5, report_edges=True, labels=True, by_weight=True, report_weight=True))
[(20, [(1, 3, 10), (3, 5, 10)]),
 (40, [(1, 2, 20), (2, 5, 20)]),
 (60, [(1, 4, 30), (4, 5, 30)])]

sage: from sage.graphs.path_enumeration import feng_k_shortest_simple_paths
sage: g = DiGraph([(1, 2, 20), (1, 3, 10), (1, 4, 30), (2, 5, 20), (3, 5, 10), (4, 5, 30), (1, 6, 100), (5, 6, 5)])
sage: list(feng_k_shortest_simple_paths(g, 1, 6, by_weight = True))
[[1, 3, 5, 6], [1, 2, 5, 6], [1, 4, 5, 6], [1, 6]]
sage: list(feng_k_shortest_simple_paths(g, 1, 6))
[[1, 6], [1, 4, 5, 6], [1, 3, 5, 6], [1, 2, 5, 6]]
sage: list(feng_k_shortest_simple_paths(g, 1, 6, report_edges=True, labels=True, by_weight=True, report_weight=True))
[(25, [(1, 3, 10), (3, 5, 10), (5, 6, 5)]),
 (45, [(1, 2, 20), (2, 5, 20), (5, 6, 5)]),
 (65, [(1, 4, 30), (4, 5, 30), (5, 6, 5)]),
 (100, [(1, 6, 100)])]
sage: list(feng_k_shortest_simple_paths(g, 1, 6, report_edges=True, labels=True, report_weight=True))
[(1, [(1, 6, 100)]),
 (3, [(1, 4, 30), (4, 5, 30), (5, 6, 5)]),
 (3, [(1, 3, 10), (3, 5, 10), (5, 6, 5)]),
 (3, [(1, 2, 20), (2, 5, 20), (5, 6, 5)])]
sage: from sage.graphs.path_enumeration import feng_k_shortest_simple_paths
sage: g = DiGraph([(1, 2, 5), (2, 3, 0), (1, 4, 2), (4, 5, 1), (5, 3, 0)])
sage: list(feng_k_shortest_simple_paths(g, 1, 3, by_weight=True))
[[1, 4, 5, 3], [1, 2, 3]]
sage: list(feng_k_shortest_simple_paths(g, 1, 3))
[[1, 2, 3], [1, 4, 5, 3]]
sage: list(feng_k_shortest_simple_paths(g, 1, 3, report_weight=True))
[(2, [1, 2, 3]), (3, [1, 4, 5, 3])]
sage: list(feng_k_shortest_simple_paths(g, 1, 3, report_weight=True, report_edges=True))
[(2, [(1, 2), (2, 3)]), (3, [(1, 4), (4, 5), (5, 3)])]
sage: list(feng_k_shortest_simple_paths(g, 1, 3, report_weight=True, report_edges=True, by_weight=True))
[(3, [(1, 4), (4, 5), (5, 3)]), (5, [(1, 2), (2, 3)])]
sage: list(feng_k_shortest_simple_paths(g, 1, 3, report_weight=True, report_edges=True, by_weight=True, labels=True))
[(3, [(1, 4, 2), (4, 5, 1), (5, 3, 0)]), (5, [(1, 2, 5), (2, 3, 0)])]

>>> from sage.all import *
>>> from sage.graphs.path_enumeration import feng_k_shortest_simple_paths
>>> g = DiGraph([(Integer(1), Integer(2), Integer(20)), (Integer(1), Integer(3), Integer(10)), (Integer(1), Integer(4), Integer(30)), (Integer(2), Integer(5), Integer(20)), (Integer(3), Integer(5), Integer(10)), (Integer(4), Integer(5), Integer(30))])
>>> list(feng_k_shortest_simple_paths(g, Integer(1), Integer(5), by_weight=True))
[[1, 3, 5], [1, 2, 5], [1, 4, 5]]
>>> list(feng_k_shortest_simple_paths(g, Integer(1), Integer(5)))
[[1, 4, 5], [1, 3, 5], [1, 2, 5]]
>>> list(feng_k_shortest_simple_paths(g, Integer(1), Integer(1)))
[[1]]
>>> list(feng_k_shortest_simple_paths(g, Integer(1), Integer(5), report_edges=True, labels=True))
[[(1, 4, 30), (4, 5, 30)], [(1, 3, 10), (3, 5, 10)], [(1, 2, 20), (2, 5, 20)]]
>>> list(feng_k_shortest_simple_paths(g, Integer(1), Integer(5), report_edges=True, labels=True, by_weight=True))
[[(1, 3, 10), (3, 5, 10)], [(1, 2, 20), (2, 5, 20)], [(1, 4, 30), (4, 5, 30)]]
>>> list(feng_k_shortest_simple_paths(g, Integer(1), Integer(5), report_edges=True, labels=True, by_weight=True, report_weight=True))
[(20, [(1, 3, 10), (3, 5, 10)]),
 (40, [(1, 2, 20), (2, 5, 20)]),
 (60, [(1, 4, 30), (4, 5, 30)])]

>>> from sage.graphs.path_enumeration import feng_k_shortest_simple_paths
>>> g = DiGraph([(Integer(1), Integer(2), Integer(20)), (Integer(1), Integer(3), Integer(10)), (Integer(1), Integer(4), Integer(30)), (Integer(2), Integer(5), Integer(20)), (Integer(3), Integer(5), Integer(10)), (Integer(4), Integer(5), Integer(30)), (Integer(1), Integer(6), Integer(100)), (Integer(5), Integer(6), Integer(5))])
>>> list(feng_k_shortest_simple_paths(g, Integer(1), Integer(6), by_weight = True))
[[1, 3, 5, 6], [1, 2, 5, 6], [1, 4, 5, 6], [1, 6]]
>>> list(feng_k_shortest_simple_paths(g, Integer(1), Integer(6)))
[[1, 6], [1, 4, 5, 6], [1, 3, 5, 6], [1, 2, 5, 6]]
>>> list(feng_k_shortest_simple_paths(g, Integer(1), Integer(6), report_edges=True, labels=True, by_weight=True, report_weight=True))
[(25, [(1, 3, 10), (3, 5, 10), (5, 6, 5)]),
 (45, [(1, 2, 20), (2, 5, 20), (5, 6, 5)]),
 (65, [(1, 4, 30), (4, 5, 30), (5, 6, 5)]),
 (100, [(1, 6, 100)])]
>>> list(feng_k_shortest_simple_paths(g, Integer(1), Integer(6), report_edges=True, labels=True, report_weight=True))
[(1, [(1, 6, 100)]),
 (3, [(1, 4, 30), (4, 5, 30), (5, 6, 5)]),
 (3, [(1, 3, 10), (3, 5, 10), (5, 6, 5)]),
 (3, [(1, 2, 20), (2, 5, 20), (5, 6, 5)])]
>>> from sage.graphs.path_enumeration import feng_k_shortest_simple_paths
>>> g = DiGraph([(Integer(1), Integer(2), Integer(5)), (Integer(2), Integer(3), Integer(0)), (Integer(1), Integer(4), Integer(2)), (Integer(4), Integer(5), Integer(1)), (Integer(5), Integer(3), Integer(0))])
>>> list(feng_k_shortest_simple_paths(g, Integer(1), Integer(3), by_weight=True))
[[1, 4, 5, 3], [1, 2, 3]]
>>> list(feng_k_shortest_simple_paths(g, Integer(1), Integer(3)))
[[1, 2, 3], [1, 4, 5, 3]]
>>> list(feng_k_shortest_simple_paths(g, Integer(1), Integer(3), report_weight=True))
[(2, [1, 2, 3]), (3, [1, 4, 5, 3])]
>>> list(feng_k_shortest_simple_paths(g, Integer(1), Integer(3), report_weight=True, report_edges=True))
[(2, [(1, 2), (2, 3)]), (3, [(1, 4), (4, 5), (5, 3)])]
>>> list(feng_k_shortest_simple_paths(g, Integer(1), Integer(3), report_weight=True, report_edges=True, by_weight=True))
[(3, [(1, 4), (4, 5), (5, 3)]), (5, [(1, 2), (2, 3)])]
>>> list(feng_k_shortest_simple_paths(g, Integer(1), Integer(3), report_weight=True, report_edges=True, by_weight=True, labels=True))
[(3, [(1, 4, 2), (4, 5, 1), (5, 3, 0)]), (5, [(1, 2, 5), (2, 3, 0)])]
sage.graphs.path_enumeration.shortest_simple_paths(self, source, target, weight_function=None, by_weight=False, check_weight=True, algorithm=None, report_edges=False, labels=False, report_weight=False)[source]#

Return an iterator over the simple paths between a pair of vertices.

This method returns an iterator over the simple paths (i.e., without repetition) from source to target. By default (by_weight is False), the paths are reported by increasing number of edges. When by_weight is True, the paths are reported by increasing weights.

In case of weighted graphs negative weights are not allowed.

If source is the same vertex as target, then [[source]] is returned – a list containing the 1-vertex, 0-edge path source.

By default Yen's algorithm [Yen1970] is used for undirected graphs and Feng's algorithm is used for directed graphs [Feng2014].

The loops and the multiedges if present in the given graph are ignored and only minimum of the edge labels is kept in case of multiedges.

INPUT:

  • source – a vertex of the graph, where to start

  • target – a vertex of the graph, where to end

  • weight_function – function (default: None); a function that takes as input an edge (u, v, l) and outputs its weight. If not None, by_weight is automatically set to True. If None and by_weight is True, we use the edge label l as a weight.

  • by_weight – boolean (default: False); if True, the edges in the graph are weighted, otherwise all edges have weight 1

  • check_weight – boolean (default: True); whether to check that the weight_function outputs a number for each edge.

  • algorithm – string (default: None); the algorithm to use in computing k shortest paths of self. The following algorithms are supported:

    • "Yen" – Yen’s algorithm [Yen1970]

    • "Feng" – an improved version of Yen’s algorithm but that works only for directed graphs [Feng2014]

  • report_edges – boolean (default: False); whether to report paths as list of vertices (default) or list of edges. When set to False, the labels parameter is ignored.

  • labels – boolean (default: False); if False, each edge is simply a pair (u, v) of vertices. Otherwise a list of edges along with its edge labels are used to represent the path.

  • report_weight – boolean (default: False); if False, just the path between source and target is returned. Otherwise a tuple of path length and path is returned.

EXAMPLES:

sage: g = DiGraph([(1, 2, 20), (1, 3, 10), (1, 4, 30),
....:              (2, 5, 20), (3, 5, 10), (4, 5, 30)])
sage: list(g.shortest_simple_paths(1, 5, by_weight=True, algorithm="Yen"))
[[1, 3, 5], [1, 2, 5], [1, 4, 5]]
sage: list(g.shortest_simple_paths(1, 5, algorithm="Yen"))
[[1, 2, 5], [1, 3, 5], [1, 4, 5]]
sage: list(g.shortest_simple_paths(1, 1))
[[1]]
sage: list(g.shortest_simple_paths(1, 5, by_weight=True,
....:                              report_edges=True, report_weight=True, labels=True))
[(20, [(1, 3, 10), (3, 5, 10)]),
 (40, [(1, 2, 20), (2, 5, 20)]),
 (60, [(1, 4, 30), (4, 5, 30)])]
sage: list(g.shortest_simple_paths(1, 5, by_weight=True, algorithm="Feng",
....:                              report_edges=True, report_weight=True))
[(20, [(1, 3), (3, 5)]), (40, [(1, 2), (2, 5)]), (60, [(1, 4), (4, 5)])]
sage: list(g.shortest_simple_paths(1, 5, report_edges=True, report_weight=True))
[(2, [(1, 4), (4, 5)]), (2, [(1, 3), (3, 5)]), (2, [(1, 2), (2, 5)])]
sage: list(g.shortest_simple_paths(1, 5, by_weight=True, report_edges=True))
[[(1, 3), (3, 5)], [(1, 2), (2, 5)], [(1, 4), (4, 5)]]
sage: list(g.shortest_simple_paths(1, 5, by_weight=True, algorithm="Feng",
....:                              report_edges=True, labels=True))
[[(1, 3, 10), (3, 5, 10)], [(1, 2, 20), (2, 5, 20)], [(1, 4, 30), (4, 5, 30)]]
sage: g = Graph([(1, 2, 20), (1, 3, 10), (1, 4, 30), (2, 5, 20),
....:            (3, 5, 10), (4, 5, 30), (1, 6, 100), (5, 6, 5)])
sage: list(g.shortest_simple_paths(1, 6, by_weight = True))
[[1, 3, 5, 6], [1, 2, 5, 6], [1, 4, 5, 6], [1, 6]]
sage: list(g.shortest_simple_paths(1, 6, algorithm="Yen"))
[[1, 6], [1, 2, 5, 6], [1, 3, 5, 6], [1, 4, 5, 6]]
sage: list(g.shortest_simple_paths(1, 6,
....:                              report_edges=True, report_weight=True, labels=True))
[(1, [(1, 6, 100)]),
 (3, [(1, 2, 20), (2, 5, 20), (5, 6, 5)]),
 (3, [(1, 3, 10), (3, 5, 10), (5, 6, 5)]),
 (3, [(1, 4, 30), (4, 5, 30), (5, 6, 5)])]
sage: list(g.shortest_simple_paths(1, 6, by_weight=True,
....:                              report_edges=True, report_weight=True, labels=True))
[(25, [(1, 3, 10), (3, 5, 10), (5, 6, 5)]),
 (45, [(1, 2, 20), (2, 5, 20), (5, 6, 5)]),
 (65, [(1, 4, 30), (4, 5, 30), (5, 6, 5)]),
 (100, [(1, 6, 100)])]
sage: list(g.shortest_simple_paths(1, 6, by_weight=True,
....:                              report_edges=True, labels=True))
[[(1, 3, 10), (3, 5, 10), (5, 6, 5)],
 [(1, 2, 20), (2, 5, 20), (5, 6, 5)],
 [(1, 4, 30), (4, 5, 30), (5, 6, 5)],
 [(1, 6, 100)]]
sage: list(g.shortest_simple_paths(1, 6, report_edges=True, labels=True))
[[(1, 6, 100)],
 [(1, 2, 20), (2, 5, 20), (5, 6, 5)],
 [(1, 3, 10), (3, 5, 10), (5, 6, 5)],
 [(1, 4, 30), (4, 5, 30), (5, 6, 5)]]

>>> from sage.all import *
>>> g = DiGraph([(Integer(1), Integer(2), Integer(20)), (Integer(1), Integer(3), Integer(10)), (Integer(1), Integer(4), Integer(30)),
...              (Integer(2), Integer(5), Integer(20)), (Integer(3), Integer(5), Integer(10)), (Integer(4), Integer(5), Integer(30))])
>>> list(g.shortest_simple_paths(Integer(1), Integer(5), by_weight=True, algorithm="Yen"))
[[1, 3, 5], [1, 2, 5], [1, 4, 5]]
>>> list(g.shortest_simple_paths(Integer(1), Integer(5), algorithm="Yen"))
[[1, 2, 5], [1, 3, 5], [1, 4, 5]]
>>> list(g.shortest_simple_paths(Integer(1), Integer(1)))
[[1]]
>>> list(g.shortest_simple_paths(Integer(1), Integer(5), by_weight=True,
...                              report_edges=True, report_weight=True, labels=True))
[(20, [(1, 3, 10), (3, 5, 10)]),
 (40, [(1, 2, 20), (2, 5, 20)]),
 (60, [(1, 4, 30), (4, 5, 30)])]
>>> list(g.shortest_simple_paths(Integer(1), Integer(5), by_weight=True, algorithm="Feng",
...                              report_edges=True, report_weight=True))
[(20, [(1, 3), (3, 5)]), (40, [(1, 2), (2, 5)]), (60, [(1, 4), (4, 5)])]
>>> list(g.shortest_simple_paths(Integer(1), Integer(5), report_edges=True, report_weight=True))
[(2, [(1, 4), (4, 5)]), (2, [(1, 3), (3, 5)]), (2, [(1, 2), (2, 5)])]
>>> list(g.shortest_simple_paths(Integer(1), Integer(5), by_weight=True, report_edges=True))
[[(1, 3), (3, 5)], [(1, 2), (2, 5)], [(1, 4), (4, 5)]]
>>> list(g.shortest_simple_paths(Integer(1), Integer(5), by_weight=True, algorithm="Feng",
...                              report_edges=True, labels=True))
[[(1, 3, 10), (3, 5, 10)], [(1, 2, 20), (2, 5, 20)], [(1, 4, 30), (4, 5, 30)]]
>>> g = Graph([(Integer(1), Integer(2), Integer(20)), (Integer(1), Integer(3), Integer(10)), (Integer(1), Integer(4), Integer(30)), (Integer(2), Integer(5), Integer(20)),
...            (Integer(3), Integer(5), Integer(10)), (Integer(4), Integer(5), Integer(30)), (Integer(1), Integer(6), Integer(100)), (Integer(5), Integer(6), Integer(5))])
>>> list(g.shortest_simple_paths(Integer(1), Integer(6), by_weight = True))
[[1, 3, 5, 6], [1, 2, 5, 6], [1, 4, 5, 6], [1, 6]]
>>> list(g.shortest_simple_paths(Integer(1), Integer(6), algorithm="Yen"))
[[1, 6], [1, 2, 5, 6], [1, 3, 5, 6], [1, 4, 5, 6]]
>>> list(g.shortest_simple_paths(Integer(1), Integer(6),
...                              report_edges=True, report_weight=True, labels=True))
[(1, [(1, 6, 100)]),
 (3, [(1, 2, 20), (2, 5, 20), (5, 6, 5)]),
 (3, [(1, 3, 10), (3, 5, 10), (5, 6, 5)]),
 (3, [(1, 4, 30), (4, 5, 30), (5, 6, 5)])]
>>> list(g.shortest_simple_paths(Integer(1), Integer(6), by_weight=True,
...                              report_edges=True, report_weight=True, labels=True))
[(25, [(1, 3, 10), (3, 5, 10), (5, 6, 5)]),
 (45, [(1, 2, 20), (2, 5, 20), (5, 6, 5)]),
 (65, [(1, 4, 30), (4, 5, 30), (5, 6, 5)]),
 (100, [(1, 6, 100)])]
>>> list(g.shortest_simple_paths(Integer(1), Integer(6), by_weight=True,
...                              report_edges=True, labels=True))
[[(1, 3, 10), (3, 5, 10), (5, 6, 5)],
 [(1, 2, 20), (2, 5, 20), (5, 6, 5)],
 [(1, 4, 30), (4, 5, 30), (5, 6, 5)],
 [(1, 6, 100)]]
>>> list(g.shortest_simple_paths(Integer(1), Integer(6), report_edges=True, labels=True))
[[(1, 6, 100)],
 [(1, 2, 20), (2, 5, 20), (5, 6, 5)],
 [(1, 3, 10), (3, 5, 10), (5, 6, 5)],
 [(1, 4, 30), (4, 5, 30), (5, 6, 5)]]
sage.graphs.path_enumeration.yen_k_shortest_simple_paths(self, source, target, weight_function=None, by_weight=False, check_weight=True, report_edges=False, labels=False, report_weight=False)[source]#

Return an iterator over the simple paths between a pair of vertices in increasing order of weights.

For unweighted graphs paths are returned in order of increasing number of edges.

In case of weighted graphs negative weights are not allowed.

If source is the same vertex as target, then [[source]] is returned – a list containing the 1-vertex, 0-edge path source.

The loops and the multiedges if present in the given graph are ignored and only minimum of the edge labels is kept in case of multiedges.

INPUT:

  • source – a vertex of the graph, where to start

  • target – a vertex of the graph, where to end

  • weight_function – function (default: None); a function that takes as input an edge (u, v, l) and outputs its weight. If not None, by_weight is automatically set to True. If None and by_weight is True, we use the edge label l as a weight.

  • by_weight – boolean (default: False); if True, the edges in the graph are weighted, otherwise all edges have weight 1

  • check_weight – boolean (default: True); whether to check that the weight_function outputs a number for each edge

  • report_edges – boolean (default: False); whether to report paths as list of vertices (default) or list of edges, if False then labels parameter is ignored

  • labels – boolean (default: False); if False, each edge is simply a pair (u, v) of vertices. Otherwise a list of edges along with its edge labels are used to represent the path.

  • report_weight – boolean (default: False); if False, just the path between source and target is returned. Otherwise a tuple of path length and path is returned.

ALGORITHM:

This algorithm can be divided into two parts. Firstly, it determines a shortest path from source to target. Then, it determines all the other \(k\)-shortest paths. This algorithm finds the deviations of previous shortest paths to determine the next shortest paths.

Time complexity is \(O(kn(m+n\log{n}))\) where \(n\) is the number of vertices and \(m\) is the number of edges and \(k\) is the number of shortest paths needed to find.

See [Yen1970] and the Wikipedia article Yen%27s_algorithm for more details on the algorithm.

EXAMPLES:

sage: from sage.graphs.path_enumeration import yen_k_shortest_simple_paths
sage: g = DiGraph([(1, 2, 20), (1, 3, 10), (1, 4, 30), (2, 5, 20), (3, 5, 10), (4, 5, 30)])
sage: list(yen_k_shortest_simple_paths(g, 1, 5, by_weight=True))
[[1, 3, 5], [1, 2, 5], [1, 4, 5]]
sage: list(yen_k_shortest_simple_paths(g, 1, 5))
[[1, 2, 5], [1, 3, 5], [1, 4, 5]]
sage: list(yen_k_shortest_simple_paths(g, 1, 1))
[[1]]
sage: list(yen_k_shortest_simple_paths(g, 1, 5, by_weight=True, report_edges=True, report_weight=True, labels=True))
[(20, [(1, 3, 10), (3, 5, 10)]),
 (40, [(1, 2, 20), (2, 5, 20)]),
 (60, [(1, 4, 30), (4, 5, 30)])]
sage: list(yen_k_shortest_simple_paths(g, 1, 5, by_weight=True, report_edges=True, report_weight=True))
[(20, [(1, 3), (3, 5)]), (40, [(1, 2), (2, 5)]), (60, [(1, 4), (4, 5)])]
sage: list(yen_k_shortest_simple_paths(g, 1, 5, report_edges=True, report_weight=True))
[(2, [(1, 2), (2, 5)]), (2, [(1, 3), (3, 5)]), (2, [(1, 4), (4, 5)])]
sage: list(yen_k_shortest_simple_paths(g, 1, 5, by_weight=True, report_edges=True))
[[(1, 3), (3, 5)], [(1, 2), (2, 5)], [(1, 4), (4, 5)]]
sage: list(yen_k_shortest_simple_paths(g, 1, 5, by_weight=True, report_edges=True, labels=True))
[[(1, 3, 10), (3, 5, 10)], [(1, 2, 20), (2, 5, 20)], [(1, 4, 30), (4, 5, 30)]]
sage: from sage.graphs.path_enumeration import yen_k_shortest_simple_paths
sage: g = Graph([(1, 2, 20), (1, 3, 10), (1, 4, 30), (2, 5, 20), (3, 5, 10), (4, 5, 30), (1, 6, 100), (5, 6, 5)])
sage: list(yen_k_shortest_simple_paths(g, 1, 6, by_weight = True))
[[1, 3, 5, 6], [1, 2, 5, 6], [1, 4, 5, 6], [1, 6]]
sage: list(yen_k_shortest_simple_paths(g, 1, 6))
[[1, 6], [1, 2, 5, 6], [1, 3, 5, 6], [1, 4, 5, 6]]
sage: list(yen_k_shortest_simple_paths(g, 1, 6, report_edges=True, report_weight=True, labels=True))
[(1, [(1, 6, 100)]),
 (3, [(1, 2, 20), (2, 5, 20), (5, 6, 5)]),
 (3, [(1, 3, 10), (3, 5, 10), (5, 6, 5)]),
 (3, [(1, 4, 30), (4, 5, 30), (5, 6, 5)])]
sage: list(yen_k_shortest_simple_paths(g, 1, 6, report_edges=True, report_weight=True, labels=True, by_weight=True))
[(25, [(1, 3, 10), (3, 5, 10), (5, 6, 5)]),
 (45, [(1, 2, 20), (2, 5, 20), (5, 6, 5)]),
 (65, [(1, 4, 30), (4, 5, 30), (5, 6, 5)]),
 (100, [(1, 6, 100)])]
sage: list(yen_k_shortest_simple_paths(g, 1, 6, report_edges=True, labels=True, by_weight=True))
[[(1, 3, 10), (3, 5, 10), (5, 6, 5)],
 [(1, 2, 20), (2, 5, 20), (5, 6, 5)],
 [(1, 4, 30), (4, 5, 30), (5, 6, 5)],
 [(1, 6, 100)]]
sage: list(yen_k_shortest_simple_paths(g, 1, 6, report_edges=True, labels=True))
[[(1, 6, 100)],
 [(1, 2, 20), (2, 5, 20), (5, 6, 5)],
 [(1, 3, 10), (3, 5, 10), (5, 6, 5)],
 [(1, 4, 30), (4, 5, 30), (5, 6, 5)]]

>>> from sage.all import *
>>> from sage.graphs.path_enumeration import yen_k_shortest_simple_paths
>>> g = DiGraph([(Integer(1), Integer(2), Integer(20)), (Integer(1), Integer(3), Integer(10)), (Integer(1), Integer(4), Integer(30)), (Integer(2), Integer(5), Integer(20)), (Integer(3), Integer(5), Integer(10)), (Integer(4), Integer(5), Integer(30))])
>>> list(yen_k_shortest_simple_paths(g, Integer(1), Integer(5), by_weight=True))
[[1, 3, 5], [1, 2, 5], [1, 4, 5]]
>>> list(yen_k_shortest_simple_paths(g, Integer(1), Integer(5)))
[[1, 2, 5], [1, 3, 5], [1, 4, 5]]
>>> list(yen_k_shortest_simple_paths(g, Integer(1), Integer(1)))
[[1]]
>>> list(yen_k_shortest_simple_paths(g, Integer(1), Integer(5), by_weight=True, report_edges=True, report_weight=True, labels=True))
[(20, [(1, 3, 10), (3, 5, 10)]),
 (40, [(1, 2, 20), (2, 5, 20)]),
 (60, [(1, 4, 30), (4, 5, 30)])]
>>> list(yen_k_shortest_simple_paths(g, Integer(1), Integer(5), by_weight=True, report_edges=True, report_weight=True))
[(20, [(1, 3), (3, 5)]), (40, [(1, 2), (2, 5)]), (60, [(1, 4), (4, 5)])]
>>> list(yen_k_shortest_simple_paths(g, Integer(1), Integer(5), report_edges=True, report_weight=True))
[(2, [(1, 2), (2, 5)]), (2, [(1, 3), (3, 5)]), (2, [(1, 4), (4, 5)])]
>>> list(yen_k_shortest_simple_paths(g, Integer(1), Integer(5), by_weight=True, report_edges=True))
[[(1, 3), (3, 5)], [(1, 2), (2, 5)], [(1, 4), (4, 5)]]
>>> list(yen_k_shortest_simple_paths(g, Integer(1), Integer(5), by_weight=True, report_edges=True, labels=True))
[[(1, 3, 10), (3, 5, 10)], [(1, 2, 20), (2, 5, 20)], [(1, 4, 30), (4, 5, 30)]]
>>> from sage.graphs.path_enumeration import yen_k_shortest_simple_paths
>>> g = Graph([(Integer(1), Integer(2), Integer(20)), (Integer(1), Integer(3), Integer(10)), (Integer(1), Integer(4), Integer(30)), (Integer(2), Integer(5), Integer(20)), (Integer(3), Integer(5), Integer(10)), (Integer(4), Integer(5), Integer(30)), (Integer(1), Integer(6), Integer(100)), (Integer(5), Integer(6), Integer(5))])
>>> list(yen_k_shortest_simple_paths(g, Integer(1), Integer(6), by_weight = True))
[[1, 3, 5, 6], [1, 2, 5, 6], [1, 4, 5, 6], [1, 6]]
>>> list(yen_k_shortest_simple_paths(g, Integer(1), Integer(6)))
[[1, 6], [1, 2, 5, 6], [1, 3, 5, 6], [1, 4, 5, 6]]
>>> list(yen_k_shortest_simple_paths(g, Integer(1), Integer(6), report_edges=True, report_weight=True, labels=True))
[(1, [(1, 6, 100)]),
 (3, [(1, 2, 20), (2, 5, 20), (5, 6, 5)]),
 (3, [(1, 3, 10), (3, 5, 10), (5, 6, 5)]),
 (3, [(1, 4, 30), (4, 5, 30), (5, 6, 5)])]
>>> list(yen_k_shortest_simple_paths(g, Integer(1), Integer(6), report_edges=True, report_weight=True, labels=True, by_weight=True))
[(25, [(1, 3, 10), (3, 5, 10), (5, 6, 5)]),
 (45, [(1, 2, 20), (2, 5, 20), (5, 6, 5)]),
 (65, [(1, 4, 30), (4, 5, 30), (5, 6, 5)]),
 (100, [(1, 6, 100)])]
>>> list(yen_k_shortest_simple_paths(g, Integer(1), Integer(6), report_edges=True, labels=True, by_weight=True))
[[(1, 3, 10), (3, 5, 10), (5, 6, 5)],
 [(1, 2, 20), (2, 5, 20), (5, 6, 5)],
 [(1, 4, 30), (4, 5, 30), (5, 6, 5)],
 [(1, 6, 100)]]
>>> list(yen_k_shortest_simple_paths(g, Integer(1), Integer(6), report_edges=True, labels=True))
[[(1, 6, 100)],
 [(1, 2, 20), (2, 5, 20), (5, 6, 5)],
 [(1, 3, 10), (3, 5, 10), (5, 6, 5)],
 [(1, 4, 30), (4, 5, 30), (5, 6, 5)]]