pybgl package#

Submodules#

pybgl.aggregated_visitor module#

class AggregatedVisitor(visitors: list = None)[source]#

Bases: object

The AggregatedVisitor allows to pack several visitors to a given algorithm designed to take a (single) visitor in parameter.

Constructor.

Parameters:: visitors (list) – A list of visitors exposing the same callbacks.

get(key: str, ret_if_not_found=None) → object[source]#

Retrieves a visitor identified by a given key from this AggregatedVisitor instance.

Parameters:

key (str) – The key identifying a visitor.
ret_if_not_found – The value to be returned if not found.

Returns:

The corresponding visitor if found, None otherwise.

keys() → set[source]#

Retrieves the set of keys identifying the visitors nested in this AggregatedVisitor instance.

Returns:: The set of keys that could be used with self.get()

static type_to_key(vis: object) → str[source]#

Builds the key corresponding to a visitor.

Parameters:: vis (object) – A visitor instance.
Returns:: The corresponding key (built according to its type).

pybgl.algebra module#

class BinaryOperator[source]#

Bases: object

BinaryOperator is the base class to implement a functor wrapping a binary operator.

class BinaryRelation[source]#

Bases: object

BinaryRelation is the base class to implement a functor wrapping a binary relation.

class ClosedMax(absorbing: float = 9223372036854775807)[source]#

Bases: ClosedOperator

BinaryOperator is the base class to implement a max operator in (R^+, max) group.

Constructor.

Parameters:: absorbing (object) – The absorbing of max.

impl(x: object, y: object) → object[source]#

Implementation method.

Parameters:

x (object) – The left operand.
y (object) – The right operand.

Returns:

max(x, y) if x and y are not self.absorbing, self.absorbing otherwise.

class ClosedMin(absorbing: float = 0)[source]#

Bases: ClosedOperator

BinaryOperator is the base class to implement a min operator in ([0, 1], min) group.

Constructor.

Parameters:: absorbing (object) – The absorbing of min.

impl(x: object, y: object) → object[source]#

Implementation method.

Parameters:

x (object) – The left operand.
y (object) – The right operand.

Returns:

min(x, y) if x and y are not self.absorbing, self.absorbing otherwise.

class ClosedOperator(absorbing: object)[source]#

Bases: BinaryOperator

Constructor.

Parameters:: absorbing (object) – The object representing the absorbing for this binary operation.

impl(x: object, y: object) → object[source]#

Implementation method. Must be overladed.

Parameters:

x (object) – The left operand.
y (object) – The right operand.

Returns:

True if x < y, False otherwise.

class ClosedPlus(absorbing: float = 9223372036854775807)[source]#

Bases: ClosedOperator

BinaryOperator is the base class to implement a + operator in (R^+, +) group.

Constructor.

Parameters:: absorbing (object) – The absorbing of +.

impl(x: float, y: float) → object[source]#

Implementation method.

Parameters:

x (object) – The left operand.
y (object) – The right operand.

Returns:

x + y if x and y are not self.absorbing, self.absorbing otherwise.

class ClosedTime(absorbing: float = 9223372036854775807)[source]#

Bases: ClosedOperator

BinaryOperator is the base class to implement a * operator in ([0, 1], *) group.

Constructor.

Parameters:: absorbing (object) – The absorbing of *.

impl(x: object, y: object) → object[source]#

Implementation method.

Parameters:

x (object) – The left operand.
y (object) – The right operand.

Returns:

x * y if x and y are not self.absorbing, self.absorbing otherwise.

class GreaterThan[source]#

Bases: BinaryRelation

Less is the functor that wraps the > binary relation.

class Less[source]#

Bases: BinaryRelation

Less is the functor that wraps the < binary relation.

pybgl.automaton module#

class Automaton(num_vertices: int = 0, q0: int = 0, pmap_vfinal: ReadPropertyMap = None)[source]#

Bases: DirectedGraph

The Automaton implements a Deterministic Finite Automaton.

Constructor.

Parameters:

num_vertices (int) – Pass the (initial) number of vertices.
q0 (int) – The vertex descriptor of the initial state.
pmap_vfinal (ReadPropertyMap) – A ReadPropertyMap that maps a vertex descriptor with a boolean which equals True if the vertex is a final state None otherwise.

accepts(w: str) → bool[source]#

Tests whether this Automaton instance accepts a word, meaning there exist a state reached from its initial state by consuming successively each character of the input word.

Parameters:: w (str) – The input word.
Returns:: True if the automaton accepts w False otherwise.

add_edge(q: int, r: int, a: str) → tuple[source]#

Adds a transition to this Automaton instance.

Parameters:

q (int) – The vertex descriptor of source state of the new transition.
r (int) – The vertex descriptor of target state of the new transition.
a (str) – The label of the new transition.

Returns:

A tuple (e, success) where e is an EdgeDescriptor compliant with this Automaton class and success == True if successful, (None, False) otherwise.

alphabet() → set[source]#

Computes the (minimal) alphabet related to this Automaton instance.

Returns:: The corresponding set of symbols.

automaton_insert_string(w: str) → int[source]#

Updates this Automaton instance by adding states and transition so that it accepts a word w.

Parameters:: w (str) – The word.
Returns:: The reached state in best effort.

delta(q: int, a: str) → int[source]#

Transition function, allowing to move from a state q to its a-successor, if any. See also Automaton.delta_word().

Parameters:

q (int) – The vertex descriptor of a state of this Automaton instance.
a (str) – The symbol.

Returns:

The reached state (if any), BOTTOM otherwise.

delta_best_effort(w: str) → tuple[source]#

Transition function, allowing to move from the initial state to the state reached by consuming each character of a word w, while possible. See also Automaton.delta_word().

Parameters:: w (str) – The word.
Returns:: The reached state in best effort.

delta_word(q: int, w: str) → int[source]#

Transition function, allowing to move from a state q to the state reached by consuming each character of a word w, if any. See also the Automaton.delta() method.

Parameters:

q (int) – The vertex descriptor of a state of this Automaton instance.
w (str) – The word.

Returns:

The reached state (if any), BOTTOM otherwise.

edge(q: int, r: int, a: str) → tuple[source]#

Retrieves the edge from a state q to state r such that r is a a-successor of q in this Automaton instance, if any.

Parameters:

q (int) – The source of the edge.
r (int) – The target of the edge.

Returns:

(e, True) if it exists a single edge from q to r, (None, False) otherwise.

edges() → iter[source]#

Retrieves an iterator over the transitions involved in this Automaton instance.

Returns:: An iterator over the transitions.

finals() → set[source]#

Returns the vertex descriptors of the final states of this Automaton instance.

Returns:: The vertex descriptors of the final state if set, None otherwise.

in_edges(q: int)[source]#

Retrieves an iterator over the in-edges of a state q involved in this Automaton instance.

Parameters:: q (int) – The target vertex.

:raises RuntimeError` as a Automaton must no: :raises support this primitive. If you require it, use the: :raises IncidenceAutomaton:

Returns:: An iterator over the edges of q.

initial() → int[source]#

Returns the vertex descriptor of the initial state of this Automaton instance.

Returns:: The vertex descriptor of the initial state if set, None otherwise.

is_complete() → bool[source]#

Tests whether this Automaton instance is complete or not, i.e., if each state of this automaton is has for each symbol a of its alphabet a a-successor.

Returns:: True if this Automaton is complete, False otherwise.

static is_deterministic() → bool[source]#

Tests whether this Automaton instance is deterministic or not.

Returns:: True.

is_final(q: int) → bool[source]#

Tests whether state is a final state of this Automaton instance.

Parameters:: q (int) – The vertex descriptor of the considered state.
Returns:: True if q is a final state, None otherwise.

static is_finite() → bool[source]#

Tests whether this Automaton instance is finite or not.

Returns:: True.

is_initial(q: int) → bool[source]#

Tests whether state is the initial state of this Automaton instance.

Parameters:: q (int) – The vertex descriptor of the considered state.
Returns:: True if q is the initial state, None otherwise.

label(e: EdgeDescriptor) → str[source]#

Retrieves the symbol assigned to a transition of this Automaton instance.

Parameters:: e (EdgeDescriptor) – The edge descriptor of the considered transition.
Returns:: The symbol assigned to the considered transition.

out_edges(q: int) → iter[source]#

Retrieves an iterator over the out-transitions of a state q involved in this Automaton instance.

Parameters:: q (int) – The source state.
Returns:: An iterator over the out-edges of q.

remove_edge(e: EdgeDescriptor)[source]#

Removes a transition from this Automaton instance.

Parameters:: e (EdgeDescriptor) – The edge descriptor of the transition to be removed.

set_final(q: int, is_final: bool = True)[source]#

Sets the status of a state as the final state of this Automaton instance.

Parameters:

q (int) – The vertex descriptor of the new final state.
is_final (bool) – Pass True if q must be the new final state, False otherwise.

set_initial(q: int, is_initial: bool = True)[source]#

Sets the status of a state as the initial state of this Automaton instance.

Parameters:

q (int) – The vertex descriptor of the new initial state.
is_initial (bool) – Pass True if q must be the new initial state, False otherwise.

sigma(q: int) → set[source]#

Computes sub-alphabet related to a given state of this Automaton instance.

Parameters:: q (int) – The vertex descriptor of the considered state.
Returns:: The corresponding set of symbols.

to_dot(**kwargs) → str[source]#

Exports this Automaton instance to a Graphviz string. See the to_dot() function.

Returns:: The corresponding Graphviz string.

accepts(w: str, g: Automaton) → bool[source]#

Tests whether an automaton accepts a word, meaning there exist a state reached from its initial state by consuming successively each character of the input word. See also Automaton.accepts() and accepts_debug().

Parameters:

w (str) – The input word.
g (Automaton) – The considered automaton.

Returns:

True if the automaton accepts w False otherwise.

accepts_debug(w: str, g: Automaton) → bool[source]#

Tests whether an automaton accepts a word, by printing for each consumed symbol the reached state.

Parameters:

w (str) – The input word.
g (Automaton) – The considered automaton.

Returns:

True if the automaton accepts w False otherwise.

add_edge(q: int, r: int, a: str, g: Automaton) → tuple[source]#

Adds a transition to an Automaton instance. See also Automaton.add_edge().

Parameters:

q (int) – The vertex descriptor of source state of the new transition.
r (int) – The vertex descriptor of target state of the new transition.
a (str) – The label of the new transition.
g (Automaton) – The considered automaton.

Returns:

A tuple (e, success) where e is an EdgeDescriptor compliant with this Automaton class and success == True if successful, (None, False) otherwise.

alphabet(g: Automaton) → set[source]#

Computes the (minimal) alphabet related to a Automaton instance. See also Automaton.alphabet().

Parameters:: g (Automaton) – The considered automaton.
Returns:: The corresponding set of symbols.

automaton_insert_string(g: Automaton, w: str) → int[source]#

Updates an Automaton instance by adding states and transition so that it accepts a word w.

Parameters:

g (Automaton) – The considered automaton.
w (str) – The word.

Returns:

The reached state in best effort.

delta(q: int, a: str, g: Automaton) → int[source]#

Transition function, allowing to move from a state q to its a-successor, if any. See also Automaton.delta().

Parameters:

q (int) – The vertex descriptor of a state of this Automaton instance.
a (str) – The symbol.
g (Automaton) – The considered automaton.

Returns:

The reached state (if any), BOTTOM otherwise.

delta_best_effort(g: Automaton, w: str) → tuple[source]#

Transition function, allowing to move from the initial state to the state reached by consuming each character of a word w, while possible. See also Automaton.delta_word().

Parameters:

w (str) – The word.
g (Automaton) – The considered automaton.

Returns:

The reached state in best effort.

delta_word(q: int, w: str, g: Automaton) → int[source]#

Transition function, allowing to move from a state q to the state reached by consuming each character of a word w, if any. See also Automaton.delta_word() and delta_best_effort().

Parameters:

q (int) – The vertex descriptor of a state of this Automaton instance.
w (str) – The word.
g (Automaton) – The considered automaton.

Returns:

The reached state (if any), BOTTOM otherwise.

edge(q: int, r: int, a: str, g: Automaton) → tuple[source]#

Retrieves the edge from a state q to state r in a Automaton instance, if any. See also Automaton.edge().

Parameters:

q (int) – The source of the edge.
r (int) – The target of the edge.
g (Automaton) – The considered automaton.

Returns:

(e, True) if it exists a single edge from q to r, (None, False) otherwise.

finals(g: Automaton) → set[source]#

Returns the vertex descriptors of the final states of a Automaton instance. See also Automaton.finals().

Parameters:: g (Automaton) – The considered automaton.
Returns:: The vertex descriptors of the final state if set, None otherwise.

initial(g: Automaton) → int[source]#

Returns the vertex descriptor of the initial state of a Automaton instance. See also Automaton.initial().

Parameters:: g (Automaton) – The considered automaton.
Returns:: The vertex descriptor of the initial state if set, None otherwise.

is_complete(g) → bool[source]#

Tests whether this Automaton instance is complete or not, i.e., if each state of this automaton is has for each symbol a of its alphabet a a-successor.

Returns:: True if this Automaton is complete, False otherwise.

is_deterministic(g) → bool[source]#

Tests whether an Automaton instance is deterministic or not. See also Automaton.is_deterministic().

Returns:: True.

is_final(q: int, g: Automaton) → bool[source]#

Tests whether state is a final state of a Automaton instance. See also Automaton.is_final().

Parameters:

q (int) – The vertex descriptor of the considered state.
g (Automaton) – The considered automaton.

Returns:

True if q is a final state, None otherwise.

is_finite(g) → bool[source]#

Tests whether an Automaton instance is finite or not. See also Automaton.is_finite().

Returns:: True.

is_initial(q: int, g: Automaton) → bool[source]#

Tests whether state is the initial state of a Automaton instance. See also Automaton.is_initial().

Parameters:

q (int) – The vertex descriptor of the considered state.
g (Automaton) – The considered automaton.

Returns:

True if q is the initial state, None otherwise.

is_minimal(g) → bool[source]#

label(e: EdgeDescriptor, g: Automaton) → str[source]#

Retrieves the symbol assigned to a transition of a Automaton instance. See also Automaton.label().

Parameters:

e (EdgeDescriptor) – The edge descriptor of the considered transition.
g (Automaton) – The considered automaton.

Returns:

The symbol assigned to the considered transition.

make_automaton(transitions: list, q0n: int = 0, pmap_vfinal: ~pybgl.property_map.ReadPropertyMap = None, Constructor=<class 'pybgl.automaton.Automaton'>)[source]#

Makes an automaton of type AutomatonClass according to a list of transitions. You may use any arbitrary identifier to characterize the states involved in the transitions.

Parameters:

transitions (list) – The list of transitions, where is each transition is modeled by a (qn, rn, a) tuple and where qn identifies the source of the transition rn identifies the target of the transition and a labels the transition.
q0n (int) – The identifier in transitions of the initial state.
pmap_vfinal (ReadPropertyMap) – A property map which maps each state identifier with a boolean indicating whether the state is final (True) or not (False).
Constructor – The class use to allocate the automaton. Defaults to Automaton.

Example

>>> from collections import defaultdict
>>> from pybgl import (
...      Automaton, make_assoc_property_map, make_automaton
... )
>>> transitions = [("root", "sink", "a"), ("root", "sink", "b")]
>>> map_vfinal = defaultdict(bool, {"root": False, "sink": True})
>>> g = make_automaton(
...     transitions, "root",
...     make_assoc_property_map(map_vfinal)
... )

Returns:: The corresponding automaton.

set_final(q: int, g: Automaton, is_final: bool = True)[source]#

Sets the status of a state as the final state of this Automaton instance. See also Automaton.set_final().

Parameters:

q (int) – The vertex descriptor of the new final state.
g (Automaton) – The considered automaton.
is_final (bool) – Pass True if q must be the new final state, False otherwise.

set_initial(q: int, g: Automaton, is_initial: bool = True)[source]#

Sets the status of a state as the initial state of a Automaton instance. See also Automaton.set_initial().

Parameters:

q (int) – The vertex descriptor of the new initial state.
g (Automaton) – The considered automaton.
is_initial (bool) – Pass True if q must be the new initial state, False otherwise.

sigma(q: int, g: Automaton) → set[source]#

Computes sub-alphabet related to a given state of a Automaton instance. See also Automaton.sigma().

Parameters:

q (int) – The vertex descriptor of the considered state.
g (Automaton) – The considered automaton.

Returns:

The corresponding set of symbols.

pybgl.automaton_copy module#

class AutomatonCopyVisitor(*args)[source]#

Bases: DepthFirstSearchCopyVisitor

The AutomatonCopyVisitor is the internal visitor used in automaton_copy().

Constructor.

examine_relevant_edge(e: EdgeDescriptor, g: Automaton)[source]#

Method triggered when examining a relevant edge.

Parameters:

e (EdgeDescriptor) – The examined edge.
g (Automaton) –

automaton_copy(s: int, g: Automaton, g_dup: Automaton, pmap_vrelevant: ReadPropertyMap = None, pmap_erelevant: ReadPropertyMap = None, pmap_vertices: ReadWritePropertyMap = None, pmap_edges: ReadWritePropertyMap = None, callback_dup_vertex: callable = None, callback_dup_edge: callable = None)[source]#

Copies a sub-graph from an Automaton according to an edge-based filtering starting from a given source node.

Parameters:

s (int) – The VertexDescriptor of the source node.
g (Automaton) – An Automaton instance.
pmap_vrelevant (ReadPropertyMap) – A ReadPropertyMap{VertexDescriptor : bool} which maps each vertex whether to a boolean indicating if it must be duped or not.
pmap_erelevant (ReadPropertyMap) – A ReadPropertyMap{EdgeDescriptor : bool} which maps each edge whether to a boolean indicating if it must be duped or not.
callback_dup_vertex (callable) – A Callback(u, g, u_dup, g_dup). Pass None if irrelevant.
callback_dup_edge (callable) – A Callback(e, g, e_dup, g_dup). Pass None if irrelevant.

pybgl.bk_tree module#

class BKTree(distance: callable)[source]#

Bases: Automaton

A BK-tree <https://en.wikipedia.org/wiki/BK-tree> is a metric tree suggested by Walter Austin Burkhard and Robert M. Keller specifically adapted to discrete metric spaces.

This implementation is inspired from this link.

We inherit Automaton because a BK-tree can be seen as a deterministic automaton whose alphabet it the weight assigned to its edge;

Constructor.

Parameters:: distance (callable) – An arbitrary string distance. Example: levenshtein_distance().

add_vertex(w: str) → int[source]#

Adds a vertex to this BKTree instance.

Parameters:: w (str) – The word assigned to the added node.
Returns:: The corresponding vertex descriptor.

element(u: int) → str[source]#

Retrieves the element assigned to a node of this BKTree instance.

Parameters:: u (int) – The vertex descriptor of the considered node.
Returns:: The element assigned to u.

insert(w: str, u: int = None) → int[source]#

Inserts an element in this BKTree instance from a given node.

Parameters:

w (str) – The element to be inserted.
u (int) – The vertex descriptor of the considered node. You may pass None to start from the root.

Returns:

The vertex descriptor of the word mapped to w.

search(w: str, d_max: int = 9223372036854775807, r: int = None) → tuple[source]#

Searches an element in this BKTree instance from a given node, assuming its distance with the element assigned to the root does not exceed d_max.

Parameters:

w (object) – The element to be inserted.
d_max (int) – The radius search. Defaults to INFINITY.
r (int) – The vertex descriptor of the considered node. You may pass None to start from the root.

Returns:

A pair (w_best, d_best) where w_best is the best match and d_best the distance between the root element and w_best if found, None otherwise.

to_dot(**kwargs) → str[source]#

Exports this Automaton instance to a Graphviz string. See the to_dot() function.

Returns:: The corresponding graphviz string.

add_vertex(w: str, t: BKTree) → int[source]#

Adds a vertex to a BKTree instance.

Parameters:

w (str) – The word assigned to the added node.
t (BKTree) – The considered BK-tree.

Returns:

The corresponding vertex descriptor.

bk_tree_insert(w: str, t: BKTree, u: int = None) → int[source]#

Inserts an element in a BKTree instance from a given node.

Parameters:

w (str) – The element to be inserted.
t (BKTree) –
u (int) – The vertex descriptor of the considered node. You may pass None to start from the root.

Returns:

The vertex descriptor of the word mapped to w.

make_bk_tree(elements: iter, distance: callable = None) → BKTree[source]#

Makes a BK Tree from a list of words.

Parameters:

elements – The list of elements organized in the BK-tree.
distance (callable) – The distance over the set of elements used to organize the BK-tree.

Returns:

The resulting BK-tree.

pybgl.breadth_first_search module#

class DefaultBreadthFirstSearchVisitor[source]#

Bases: object

The DefaultBreadthFirstSearchVisitor class is the base class for any visitor that can be passed to the breadth_first_search() and breadth_first_search_graph() functions.

black_target(e: EdgeDescriptor, g: Graph)[source]#

Method invoked (in addition to DefaultBreadthFirstSearchVisitor.non_tree_edge()) if the target vertex is colored BLACK at the time of examination. The color BLACK indicates that the vertex is no longer in the queue.

Parameters:

e (EdgeDescriptor) – The considered non-tree edge, pointing to a BLACK vertex.
g (Graph) – The considered graph.

discover_vertex(u: int, g: Graph)[source]#

Method invoked the first time the algorithm encounters vertex u. All vertices closer to the source vertex have been discovered, and vertices further from the source have not yet been discovered.

Parameters:

u (int) – The vertex being discovered.
g (Graph) – The considered graph.

examine_edge(e: EdgeDescriptor, g: Graph)[source]#

Method invoked invoked on every out-edge of each vertex immediately after the vertex is removed from the queue.

Parameters:

e (EdgeDescriptor) – The edge being examined.
g (Graph) – The considered graph.

examine_vertex(u: int, g: Graph)[source]#

Method invoked for each vertex as it is removed from the queue.

Parameters:

u (int) – The vertex being examined.
g (Graph) – The considered graph.

finish_vertex(u: int, g: Graph)[source]#

Method invoked after all of the out-edges of u have been examined and all of the adjacent vertices have been discovered.

Parameters:

u (int) – The vertex being finished.
g (Graph) – The considered graph.

gray_target(e: EdgeDescriptor, g: Graph)[source]#

Method invoked (in addition to DefaultBreadthFirstSearchVisitor.non_tree_edge()) if the target vertex is colored GRAY at the time of examination. The color GRAY indicates that the vertex is currently in the queue.

Parameters:

e (EdgeDescriptor) – The considered non-tree edge, pointing to a GRAY vertex.
g (Graph) – The considered graph.

initialize_vertex(u: int, g: Graph)[source]#

Method invoked on every vertex before the start of the search

Parameters:

u (int) – The vertex being initialized.
g (Graph) – The considered graph.

non_tree_edge(e: EdgeDescriptor, g: Graph)[source]#

Method invoked (in addition to DefaultBreadthFirstSearchVisitor.examine_edge()) if the edge is not a tree edge.

Parameters:

e (EdgeDescriptor) – The considered non-tree edge.
g (Graph) – The considered graph.

tree_edge(e: EdgeDescriptor, g: Graph)[source]#

Method invoked (in addition to DefaultBreadthFirstSearchVisitor.examine_edge()) if the edge is a tree edge. The target vertex of edge e is discovered at this time.

Parameters:

e (EdgeDescriptor) – The considered tree edge.
g (Graph) – The considered graph.

breadth_first_search(s: int, g: Graph, pmap_vcolor: ReadWritePropertyMap = None, vis: DefaultBreadthFirstSearchVisitor = None, if_push: callable = None)[source]#

Non-recursive implementation of the Breadth First Search, algorithm from a single source.

Based on Boost breadth_first_search by Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek.

Parameters:

g (Graph) – The graph being explored.
s (int) – The vertex descriptor of the source.
pmap_vcolor (ReadWritePropertyMap) – A property map that maps each vertex with its current color (WHITE, GRAY or BLACK)
vis (DefaultBreadthFirstSearchVisitor) – An optional visitor.
if_push (callable) – A callback(e, g) -> bool where e is the an arc of g that returns True if and only if the arc e is relevant. This is a legacy parameter. You should rather consider to filter the irrelevant arcs using the GraphView class.

breadth_first_search_graph(g: Graph, sources: iter = None, pmap_vcolor: ReadWritePropertyMap = None, vis: DefaultBreadthFirstSearchVisitor = None, if_push: callable = None)[source]#

Non-recursive implementation of the Breadth First Search algorithm, from multiple sources.

Based on Boost breadth_first_search, by Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek.

Parameters:

g (Graph) – The graph being explored.
sources (iter) – An iterable over the source vertices. Example: g.vertices().
pmap_vcolor (ReadWritePropertyMap) – A property map that maps each vertex with its current color (WHITE, GRAY or BLACK)
vis (DefaultBreadthFirstSearchVisitor) – An optional visitor.
if_push (callable) – A callback(e, g) -> bool where e is an arc of g that returns True if and only if the arc e is relevant. This is a legacy parameter. You should rather consider to filter the irrelevant arcs using the GraphView class.

pybgl.color module#

This module provides utilities related to colors, handy to convert HTML color (HSV, HSL…) to the corresponding Graphviz color. This module is complementary to colorsys.

hsl_to_hsv(hue: float, saturation: float, lightness: float) → tuple[source]#

Computes an HSL to HSV color conversion.

Parameters:

hue (float) – The hue, in [0.0, 1.0].
saturation (float) – The saturation, in [0.0, 1.0].
lightness (float) – The lightness, [0.0, 1.0].

Returns:

The corresponding HSV normalized tuple.

hsv_to_hsl(hue: float, saturation: float, value: float) → tuple[source]#

Computes an HSV to HSL color conversion.

Parameters:

hue (float) – The hue, in [0.0, 1.0].
saturation (float) – The saturation, in [0.0, 1.0].
value (float) – The value, [0.0, 1.0].

Returns:

The corresponding HSL normalized tuple.

html_color_to_graphviz(color: str) → str[source]#

HTML to Graphviz color conversion.

Parameters:: color (str) – An HTML color. Examples: "#40e0d0", "turquoise", "hsl(173, 71%, 56%)".
Returns:: The corresponding graphviz color. This is exactly color if it does not start with hsl.

normalize_color_tuple(hue: int, saturation: int, x: int) → tuple[source]#

Normalizes an HSV or HSL tuple.

Parameters:

hue (int) – The hue, in {0, …, 360}.
saturation (int) – The saturation, in {0, …, 100}.
x (int) – The value or the lightness, {0, …, 100}.

Returns:

The corresponding normalized tuple.

pybgl.cut module#

cut(s: int, g: Graph, in_cut: callable) → set[source]#

Finds a vertex cut given an edge cut.

Parameters:

s (int) – The VertexDescriptor corresponding to the source vertex.
g (Graph) – An acyclic graph.
in_cut (callable) – A Callback(EdgeDescriptor, Graph) -> bool, indicating whether an edge belong to the considered cut.

Returns:

The set of vertices that are in the vertex cut.

pybgl.damerau_levenshtein_distance module#

class DamerauLevenshteinDistance(x: str, y: str)[source]#

Bases: object

The DamerauLevenshteinDistance class is used to implement the memoization used by the damerau_levenshtein_distance_naive() function.

Constructor.

Parameters:

x (str) – The left operand.
y (str) – The right operand.

compute(i: int = 0, j: int = 0) → int[source]#

Computes the Damerau Levenshtein distance, with memoization.

Parameters:

i (int) – The current index in self.x.
j (int) – The current index in self.y.

Returns:

The minimal number of insertion/deletion/substitution/swap operations needed to transform x into y.

damerau_levenshtein_distance(x: str, y: str) → int[source]#

Computes the Damerau Levenshtein distance, with memoization.

Parameters:

x (str) – The left operand.
y (str) – The right operand.

Returns:

The minimal number of insertion/deletion/substitution/swap operations needed to transform x into y.

damerau_levenshtein_distance_naive(x: str, y: str) → int[source]#

Inefficient implementation of the Damerau Levenshtein distance (no memoization). Prefer the damerau_levenshtein_distance() function.

Parameters:

x (str) – The left operand.
y (str) – The right operand.

Returns:

The minimal number of insertion/deletion/substitution/swap operations needed to transform x into y.

pybgl.depth_first_search module#

class DefaultDepthFirstSearchVisitor[source]#

Bases: object

The DefaultDepthFirstSearchVisitor class is the base class for any visitor that can be passed to the depth_first_search() and depth_first_search_graph() functions.

back_edge(e: EdgeDescriptor, g: Graph)[source]#

Method invoked on the back edges in the graph.

Parameters:

e (EdgeDescriptor) – The considered back edge.
g (Graph) – The considered graph.

discover_vertex(u: int, g: Graph)[source]#

Method invoked when a vertex is encountered for the first time.

Parameters:

u (int) – The vertex being discovered.
g (Graph) – The considered graph.

examine_edge(e: EdgeDescriptor, g: Graph)[source]#

Method invoked on every out-edge of each vertex after it is discovered.

Parameters:

e (EdgeDescriptor) – The edge being examined.
g (Graph) – The considered graph.

finish_vertex(u: int, g: Graph)[source]#

Method invoked on a vertex after all of its out edges have been added to the search tree and all of the adjacent vertices have been discovered (but before their out-edges have been examined).

Parameters:

u (int) – The vertex being finished.
g (Graph) – The considered graph.

forward_or_cross_edge(e: EdgeDescriptor, g: Graph)[source]#

Method invoked on forward or cross edges in the graph. In an undirected graph this method is never called.

Parameters:

e (EdgeDescriptor) – The considered edge.
g (Graph) – The considered graph.

initialize_vertex(u: int, g: Graph)[source]#

Method invoked on every vertex before the start of the search

Parameters:

u (int) – The vertex being initialized.
g (Graph) – The considered graph.

start_vertex(s: int, g: Graph)[source]#

Method invoked on the source vertex once before the start of the search.

Parameters:

s (int) – The source vertex.
g (Graph) – The considered graph.

tree_edge(e: EdgeDescriptor, g: Graph)[source]#

Method invoked on each edge as it becomes a member of the edges that form the search tree. If you wish to record predecessors, do so at this event point.

Parameters:

e (EdgeDescriptor) – The considered tree edge.
g (Graph) – The considered graph.

depth_first_search(s: int, g: Graph, pmap_vcolor: ReadWritePropertyMap = None, vis: DefaultDepthFirstSearchVisitor = None, if_push: callable = None)[source]#

Non-recursive implementation of the Depth First Search algorithm, from a single source.

Based on depth_first_search.hpp, by Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek

Parameters:

s (int) – The vertex descriptor of the source vertex.
g (Graph) – The graph being explored.
pmap_vcolor (ReadWritePropertyMap) – A property map that maps each vertex with its current color (WHITE, GRAY or BLACK)
vis (DefaultBreadthFirstSearchVisitor) – An optional visitor.
if_push (callable) – A callback(e, g) -> bool where e is an arc of g that returns True if and only if the arc e is relevant. This is a legacy parameter. You should rather consider to filter the irrelevant arcs using the GraphView class.

depth_first_search_graph(g: Graph, sources: iter = None, pmap_vcolor: ReadWritePropertyMap = None, vis: DefaultDepthFirstSearchVisitor = None, if_push: bool = None)[source]#

Non-recursive implementation of the Depth First Search algorithm, from multiple sources.

Based on depth_first_search.hpp, by Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek

Parameters:

g (Graph) – The graph being explored.
sources (iter) – An iterable over the sources, e.g., g.vertices().
pmap_vcolor (ReadWritePropertyMap) – A property map that maps each vertex with its current color (WHITE, GRAY or BLACK)
vis (DefaultBreadthFirstSearchVisitor) – An optional visitor.
if_push (callable) – A callback(e, g) -> bool where e is the an arc of g that returns True if and only if the arc e is relevant. This is a legacy parameter. You should rather consider to filter the irrelevant arcs using the GraphView class.

pybgl.deterministic_inclusion module#

exception ContradictionException[source]#

Bases: RuntimeError

Exception raised when an automaton cannot be included in another one.

class DeterministicInclusionVisitor[source]#

Bases: ParallelBreadthFirstSearchVisitor

The DeterministicInclusionVisitor class is used to implement the deterministic_inclusion() function.

Constructor.

discover_vertex(q1: int, g1: Automaton, q2: int, g2: Automaton)[source]#

Method invoked when discovering the first time a (q1, q2) pair of states.

Parameters:

q1 (int) – A state of g1.
g1 (Automaton) – The automaton corresponding to left operand of the inclusion.
q2 (int) – A state of g2.
g2 (Automaton) – The automaton corresponding to right operand of the inclusion.

start_vertex(s1: int, g1: Automaton, s2: int, g2: Automaton)[source]#

Method invoked when processing the initial pair of initial states.

Parameters:

s1 (int) – A initial state of g1.
g1 (Automaton) – The automaton corresponding to left operand of the inclusion.
s2 (int) – A initial of g2.
g2 (Automaton) – The automaton corresponding to right operand of the inclusion.

update(q1: int, g1: Automaton, q2: int, g2: Automaton)[source]#

Internal method, invoked when processing a (q1, q2) pair of states.

Parameters:

q1 (int) – A state of g1.
g1 (Automaton) – The automaton corresponding to left operand of the inclusion.
q2 (int) – A state of g2.
g2 (Automaton) – The automaton corresponding to right operand of the inclusion.

deterministic_inclusion(g1: Automaton, g2: Automaton, vis: DeterministicInclusionVisitor = None) → int[source]#

Tests whether the language of a deterministic automaton is included in the language of another deterministic automaton.

Parameters:

g1 (Automaton) – The left operand.
g2 (Automaton) – The right operand.
vis – A DeterministicInclusionVisitor instance or None.

Returns:

1 if L(g1) c L(g2)
0 if L(g1) = L(g2)
-1 if L(g2) c L(g1)
None otherwise (i.e. L(g1) - L(g2) and L(g2) - L(g1) are
not empty.

pybgl.deterministic_intersection module#

class DeterministicIntersectionVisitor(g12: Automaton)[source]#

Bases: ParallelBreadthFirstSearchVisitor, ProductMixin

The DeterministicIntersectionVisitor class is used to implement the deterministic_intersection() function.

Constructor.

Parameters:: g12 (Automaton) – Pass an empty automaton, that will contain in the end the intersection automaton.

examine_edge(e1: EdgeDescriptor, g1: Automaton, e2: EdgeDescriptor, g2: Automaton, a: str)[source]#

Method invoked when examining a pair of transitions for the first time.

Parameters:

e1 (int) – A transition of g1.
g1 (Automaton) – The automaton corresponding to left operand of the intersection.
e2 (int) – A transition of g2.
g2 (Automaton) – The automaton corresponding to right operand of the intersection.
a (str) – The symbol that labels e1 and e2.

deterministic_intersection(g1: Automaton, g2: Automaton, g12: Automaton = None, vis: DeterministicIntersectionVisitor = None)[source]#

Computes the deterministic intersection of two deterministic finite automata.

Parameters:

g1 (Automaton) – The left operand of the deterministic intersection.
g1 – The right operand of the deterministic intersection.
g12 (Automaton) – The output automata. Pass an empty automaton. In the end, it will be the intersection automaton.
vis (DeterministicIntersectionVisitor) – An optional visitor.

pybgl.deterministic_union module#

class DeterministicUnionVisitor(g12: Automaton)[source]#

Bases: ParallelBreadthFirstSearchVisitor, ProductMixin

The DeterministicUnionVisitor class is used to implement the deterministic_union() function.

Constructor.

Parameters:: g12 (Automaton) – Pass an empty automaton, that will contain in the end the union automaton.

examine_edge(e1: EdgeDescriptor, g1: Automaton, e2: EdgeDescriptor, g2: Automaton, a: str)[source]#

Method invoked when examining a pair of transitions for the first time.

Parameters:

e1 (int) – A transition of g1.
g1 (Automaton) – The automaton corresponding to left operand of the union.
e2 (int) – A transition of g2.
g2 (Automaton) – The automaton corresponding to right operand of the union.
a (str) – The symbol that labels e1 and e2.

deterministic_union(g1: Automaton, g2: Automaton, g12: Automaton = None, vis: DeterministicUnionVisitor = None)[source]#

Computes the deterministic union of two deterministic finite automata.

Parameters:

g1 (Automaton) – The left operand of the deterministic union.
g1 – The right operand of the deterministic union.
g12 (Automaton) – The output automata. Pass an empty automaton. In the end, it will be the union automaton.
vis (DeterministicUnionVisitor) – An optional visitor.

pybgl.digital_sequence module#

class DigitalSequence(w: str)[source]#

Bases: Trie

The DigitalSequence wraps a string to make it compabible with any function of pybgl that applies to a Trie instance (and hence to a Automaton instance).

Constructor.

Parameters:: w (str) – The wrapped string.

add_edge(*args)[source]#

Adds a transition to this Automaton instance.

Parameters:

q (int) – The vertex descriptor of source state of the new transition.
r (int) – The vertex descriptor of target state of the new transition.
a (str) – The label of the new transition.

Returns:

A tuple (e, success) where e is an EdgeDescriptor compliant with this Automaton class and success == True if successful, (None, False) otherwise.

add_vertex(*args)[source]#

Adds a vertex to this Graph instance.

Returns:: The vertex descriptor of the added vertex.

alphabet() → set[source]#

Computes the (minimal) alphabet related to this Automaton instance.

Returns:: The corresponding set of symbols.

delta(q: int, a: str)[source]#

Transition function, allowing to move from a state q to its a-successor, if any. See also Automaton.delta_word().

Parameters:

q (int) – The vertex descriptor of a state of this Automaton instance.
a (str) – The symbol.

Returns:

The reached state (if any), BOTTOM otherwise.

edges() → iter[source]#

Retrieves an iterator over the transitions involved in this Automaton instance.

Returns:: An iterator over the transitions.

in_edges(q: int) → iter[source]#

Retrieves an iterator over the in-edges of a state q involved in this Automaton instance.

Parameters:: q (int) – The target vertex.

:raises RuntimeError` as a Automaton must no: :raises support this primitive. If you require it, use the: :raises IncidenceAutomaton:

Returns:: An iterator over the edges of q.

initial() → int[source]#

Returns the vertex descriptor of the initial state of this Automaton instance.

Returns:: The vertex descriptor of the initial state if set, None otherwise.

insert(w: str)[source]#

Parameters:: x (str or Trie) – A str or a Trie instance, inserted in this Trie instance.

is_final(q: int) → bool[source]#

Tests whether state is a final state of this Automaton instance.

Parameters:: q (int) – The vertex descriptor of the considered state.
Returns:: True if q is a final state, None otherwise.

is_initial(q) → bool[source]#

Tests whether state is the initial state of this Automaton instance.

Parameters:: q (int) – The vertex descriptor of the considered state.
Returns:: True if q is the initial state, None otherwise.

num_edges() → int[source]#

Counts the number of edges involved in this Graph instance.

Returns:: The number of edges.

num_vertices() → int[source]#

Counts the number of vertices involved in this Graph instance.

Returns:: The number of vertices.

out_edges(q: int) → iter[source]#

Retrieves an iterator over the out-transitions of a state q involved in this Automaton instance.

Parameters:: q (int) – The source state.
Returns:: An iterator over the out-edges of q.

remove_edge(*args)[source]#

Removes a transition from this Automaton instance.

Parameters:: e (EdgeDescriptor) – The edge descriptor of the transition to be removed.

remove_vertex(*args)[source]#

Removes a vertex from this Graph instance.

Parameters:: u (int) – The vertex descriptor of the vertex to be removed.
Raises:: KeyError –

set_final()[source]#

Sets the status of a state as the final state of this Automaton instance.

Parameters:

q (int) – The vertex descriptor of the new final state.
is_final (bool) – Pass True if q must be the new final state, False otherwise.

set_initial()[source]#

Sets the status of a state as the initial state of this Automaton instance.

Parameters:

q (int) – The vertex descriptor of the new initial state.
is_initial (bool) – Pass True if q must be the new initial state, False otherwise.

sigma(q: int) → iter[source]#

Computes sub-alphabet related to a given state of this Automaton instance.

Parameters:: q (int) – The vertex descriptor of the considered state.
Returns:: The corresponding set of symbols.

vertices() → iter[source]#

Gets an iterator over the vertices involved in this Graph instance.

Returns:: An iterator over the vertices.

pybgl.dijkstra_shortest_paths module#

exception DijkstraStopException[source]#: Bases: Exception

class DijkstraTowardsVisitor(t: int)[source]#

Bases: DijkstraVisitor

The DijkstraTowardsVisitor may be passed to the dijkstra_shortest_paths() function to abort computation once the cost of the shortest path to t is definitely known.

Important notes:

stopping when discovering t (the first time) does not guarantee that we have find the shortest path towards t. We must wait the DijkstraVisitor.examine_vertex() method to be triggered.
stopping when discovering a vertex u farther than t from s always occurs after finishing vertex t.

As a sequel, we must wait that t is examined to guarantee that a a shortest path to t has been explored.

examine_vertex(u: int, g: Graph)[source]#

Method invoked on a vertex as it is removed from the priority queue and added to set of vertices to process. At this point, we know that (pred[u], u) is a shortest-paths tree edge so d[u] = d(s, u) = d[pred[u]] + w(pred[u], u). Also, the distances of the examined vertices is monotonically increasing d[u1] <= d[u2] <= d[un].

Parameters:

u (int) – The examined vertex.
g (Graph) – The considered graph.

class DijkstraVisitor[source]#

Bases: object

The DijkstraVisitor class is the base class for any visitor that can be passed to the dijkstra_shortest_path() and dijkstra_shortest_paths() functions.

discover_vertex(u: int, g: Graph)[source]#

Method invoked on vertex v when an edge (u, v) is examined and v is WHITE. Since a vertex is colored GRAY when it is discovered, each reacable vertex is discovered exactly once. This is also when the vertex is inserted into the priority queue.

Parameters:

u (int) – The discovered vertex.
g (Graph) – The considered graph.

edge_not_relaxed(e: EdgeDescriptor, g: Graph)[source]#

Method invoked if the edge is not relaxed (see above).

Parameters:

e (EdgeDescriptor) – The not-relaxed edge.
g (Graph) – The considered graph.

edge_relaxed(e: EdgeDescriptor, g: Graph)[source]#

Method invoked on edge (u, v) if d[u] + w(u,v) < d[v]. The edge (u, v) that participated in the last relaxation for vertex v is an edge in the shortest paths tree.

Parameters:

e (EdgeDescriptor) – The relaxed edge.
g (Graph) – The considered graph.

examine_edge(e: EdgeDescriptor, g: Graph)[source]#

Method invoked on each out-edge of a vertex immediately after it has been added to set of vertices to process.

Parameters:

e (EdgeDescriptor) – The examined edge.
g (Graph) – The considered graph.

examine_vertex(u: int, g: Graph)[source]#

Parameters:

u (int) – The examined vertex.
g (Graph) – The considered graph.

finish_vertex(u: int, g: Graph)[source]#

Method invoked on a vertex after all of its out edges have been examined.

Parameters:

u (int) – The discovered vertex.
g (Graph) – The considered graph.

initialize_vertex(u: int, g: Graph)[source]#

Method invoked on each vertex in the graph when the algorithm starts.

Parameters:

u (int) – The initialized vertex.
g (Graph) – The considered graph.

dijkstra_shortest_path(g: ~pybgl.graph.Graph, s: int, t: int, pmap_eweight: ~pybgl.property_map.ReadPropertyMap, pmap_vpreds: ~pybgl.property_map.ReadWritePropertyMap, pmap_vdist: ~pybgl.property_map.ReadWritePropertyMap, pmap_vcolor: ~pybgl.property_map.ReadWritePropertyMap = None, compare: ~pybgl.algebra.BinaryRelation = <pybgl.algebra.Less object>, combine: ~pybgl.algebra.BinaryOperator = <pybgl.algebra.ClosedPlus object>, zero: int = 0, infty: int = 9223372036854775807, vis: ~pybgl.dijkstra_shortest_paths.DijkstraVisitor = None) → list[source]#

Helper to find a single shortest path from s to t.

Parameters:

g (Graph) – The input graph.
s (int) – The vertex descriptor of the source node.
t (int) – The target descriptor of the source node.
pmap_eweight (ReadPropertyMap) – A ReadPropertyMap{EdgeDescriptor: Distance} which map each edge with its weight.
pmap_vpreds (ReadWritePropertyMap) – A ReadWritePropertyMap{VertexDescriptor: EdgeDescriptor} which will map each vertex with its incident arcs in the shortest path Directed Acyclic Graph. Each element must be initially mapped with set().
pmap_vdist (ReadWritePropertyMap) – A ReadWritePropertyMap{VertexDescriptor: Distance} which will map each vertex with the weight of its shortest path(s) from s. Each element must be initialized to zero.
pmap_vcolor (ReadWritePropertyMap) – A ReadWritePropertyMap{VertexDescriptor: Distance} which will map each vertex with the weight of its color. Each element must be initialized to WHITE.
compare (BinaryRelation) – The binary relation that compares two weight. This corresponds to the oplus operator in the semi-ring (e.g, min).
combine (BinaryOperator) – The binary relation that combines two weight. This corresponds to the otimes operator in the semi-ring (e.g, +).
zero (float) – The null distance (e.g., 0).
infty (float) – The infinite distance` (e.g., INFINITY).
vis (DijkstraVisitor) – An optional visitor.

dijkstra_shortest_paths(g: ~pybgl.graph.Graph, s: int, pmap_eweight: ~pybgl.property_map.ReadPropertyMap, pmap_vpreds: ~pybgl.property_map.ReadWritePropertyMap, pmap_vdist: ~pybgl.property_map.ReadWritePropertyMap, pmap_vcolor: ~pybgl.property_map.ReadWritePropertyMap = None, compare: ~pybgl.algebra.BinaryRelation = None, combine: ~pybgl.algebra.BinaryOperator = <pybgl.algebra.ClosedPlus object>, zero: int = 0, infty: int = 9223372036854775807, vis: ~pybgl.dijkstra_shortest_paths.DijkstraVisitor = None)[source]#

Computes the shortest path in a graph from a given source node and according to the (Distance, compare, combine) semi-ring using the Dijkstra algorithm.

Parameters:

g (Graph) – The input graph.
s (int) – The vertex descriptor of the source node.
pmap_eweight (ReadPropertyMap) – A ReadPropertyMap{EdgeDescriptor: Distance} which map each edge with its weight.
pmap_vpreds (ReadWritePropertyMap) – A ReadWritePropertyMap{VertexDescriptor: EdgeDescriptor} which will map each vertex with its incident arcs in the shortest path Directed Acyclic Graph. Each element must be initially mapped with set().
pmap_vdist (ReadWritePropertyMap) – A ReadWritePropertyMap{VertexDescriptor: Distance} which will map each vertex with the weight of its shortest path(s) from s. Each element must be initialized to zero.
pmap_vcolor (ReadWritePropertyMap) – A ReadWritePropertyMap{VertexDescriptor: Distance} which will map each vertex with the weight of its color. Each element must be initialized to WHITE.
compare (BinaryRelation) – The binary relation that compares two weight. This corresponds to the oplus operator in the semi-ring (e.g, min).
combine (BinaryOperator) – The binary relation that combines two weight. This corresponds to the otimes operator in the semi-ring (e.g, +).
zero (float) – The null distance (e.g., 0).
infty (float) – The infinite distance` (e.g., INFINITY).
vis (DijkstraVisitor) – An optional visitor.

Example

>>> g = Graph(2)
>>> e, _ = add_edge(0, 1, g)
>>> map_eweight[e] = 10
>>> map_vpreds = defaultdict(set)
>>> map_vdist = dict()
>>> dijkstra_shortest_paths(
...    g, u,
...    make_assoc_property_map(map_eweight),
...    make_assoc_property_map(map_vpreds),
...    make_assoc_property_map(map_vdist)
... )

dijkstra_shortest_paths_initialization(g: Graph, s: int, pmap_vcolor: ReadWritePropertyMap, pmap_vdist: ReadWritePropertyMap, zero: int, infty: int, vis: DijkstraVisitor = None)[source]#

dijkstra_shortest_paths_iteration(heap: ~pybgl.heap.Heap, g: ~pybgl.graph.Graph, pmap_eweight: ~pybgl.property_map.ReadPropertyMap, pmap_vpreds: ~pybgl.property_map.ReadWritePropertyMap, pmap_vdist: ~pybgl.property_map.ReadWritePropertyMap, pmap_vcolor: ~pybgl.property_map.ReadWritePropertyMap, compare: ~pybgl.algebra.BinaryRelation = <pybgl.algebra.Less object>, combine: ~pybgl.algebra.BinaryOperator = <pybgl.algebra.ClosedPlus object>, vis: ~pybgl.dijkstra_shortest_paths.DijkstraVisitor = <pybgl.dijkstra_shortest_paths.DijkstraVisitor object>)[source]#: Implementation function. See the dijkstra_shortest_paths() function.

make_shortest_path(g: Graph, s: int, t: int, pmap_vpreds: ReadPropertyMap) → list[source]#

Extracts the path from s to t in a graph g given the predecessors map computed using :py:func`dijkstra_shortest_paths` from s.

Parameters:

g (Graph) – The input graph.
s (int) – The target’s vertex descriptor.
t (int) – The target’s vertex descriptor.
pmap_vpreds (ReadPropertyMap) – A ReadPropertyMap{int: set(int)} mapping each vertex with its set of (direct) predecessors.

Returns:

A list of consecutive arcs forming a shortest path from s of t. If several shortest paths exist from s to t, this function returns an arbitrary shortest path.

make_shortest_paths_dag(g: Graph, s: int, t: int, pmap_vpreds: ReadPropertyMap, single_path: bool = False) → set[source]#

Extracts the set of arcs related to shortest paths from s to t in a graph g given the predecessors map computed using dijkstra_shortest_paths() from s. The corresponding subgraph is a DAG where the source is s and the sink is t.

Parameters:

g (Graph) – The input graph.
s (int) – The source vertex descriptor.
t (int) – The target vertex descriptor.
pmap_vpreds (ReadPropertyMap) – The ReadPropertyMap{int: set(int)} mapping each vertex with its set of (direct) predecessors.
single_path (bool) – Pass True to extract an arbitrary single shortest path, False to extract of all them. Note that if single_path is True and if multiple paths exist from s to t, make_dag() extracts an arbitrary shortest path instead of all of them.

Returns:

The corresponding set of arcs.

pybgl.graph module#

class DirectedGraph(num_vertices: int = 0)[source]#

Bases: Graph

The DirectedGraph models a directed graph. See also the UndirectedGraph class.

Constructor.

Parameters:: num_vertices (int) – Pass the (initial) number of vertices.

class EdgeDescriptor(u: int, v: int, distinguisher: int)[source]#

Bases: object

Constructor.

Never call explicitely this constructor. You are supposed a method like Graph.edges(), Graph.out_edges(), etc.

Parameters:

u (int) – The source vertex.
v (int) – The target vertex.
n (int) – The distinguisher (if several edge may exist from u to v).

class Graph(directed: bool = None, num_vertices: int = 0)[source]#

Bases: object

Graph implements base class used to implement the DirectedGraph and the UndirectedGraph classes.

Constructor.

Parameters:

directed (bool) – Pass True if the graph is directed, False otherwise.
num_vertices (int) – Pass the (initial) number of vertices.

add_edge(u: int, v: int) → tuple[source]#

Adds an edge to this Graph instance.

Parameters:

u (int) – The vertex descriptor of source vertex of the new edge.
v (int) – The vertex descriptor of target vertex of the new edge.

Returns:

A tuple (e, success) where e is an EdgeDescriptor compliant with this Graph class and success == True if successful, (None, False) otherwise.

add_vertex() → int[source]#

Adds a vertex to this Graph instance.

Returns:: The vertex descriptor of the added vertex.

edge(u: int, v: int) → tuple[source]#

Retrieves the edge from a vertex u to vertex v, if any.

Parameters:

u (int) – The source of the edge.
v (int) – The target of the edge.

Returns:

(e, True) if it exists a single edge from u to v, (None, False) otherwise.

edges() → iter[source]#

Gets an iterator over the edges involved in this Graph instance.

Returns:: An iterator over the edges.

has_edge() → bool[source]#

Checks if this Graph instance contains at least one edge.

Returns:: True if the graph has at least one edge, False otherwise.

has_vertex() → bool[source]#

Checks if this Graph contains at least one vertex.

Returns:: True if the graph has at least one vertex, False otherwise.

in_degree(u: int) → int[source]#

Gets the in-degree (the number of in-edges) of a vertex u involved in this Graph instance.

Parameters:: u (int) – The considered vertex.
Returns:: The in-degree of u

in_edges(u: int) → iter[source]#

Gets an iterator over the in-edges of a vertex v involved in this Graph instance.

Parameters:: v (int) – The target vertex.
Returns:: An iterator over the out-edges of v.

num_edges() → int[source]#

Counts the number of edges involved in this Graph instance.

Returns:: The number of edges.

num_vertices() → int[source]#

Counts the number of vertices involved in this Graph instance.

Returns:: The number of vertices.

out_degree(u: int) → int[source]#

Gets the out-degree (the number of out-edges) of a vertex u involved in this Graph instance.

Parameters:: u (int) – The considered vertex.
Returns:: The out-degree of u

out_edges(u: int) → iter[source]#

Gets an iterator over the out-edges of a vertex u involved in this Graph instance.

Parameters:: u (int) – The source vertex.
Returns:: An iterator over the out-edges of u.

remove_edge(e: EdgeDescriptor)[source]#

Removes an edge from this Graph instance.

Parameters:: e (EdgeDescriptor) – The edge descriptor of the edge to be removed.

remove_vertex(u: int)[source]#

Removes a vertex from this Graph instance.

Parameters:: u (int) – The vertex descriptor of the vertex to be removed.
Raises:: KeyError –

source(e: EdgeDescriptor) → int[source]#

Retrieves the source vertex of an arc in this Graph instance.

Parameters:: e (EdgeDescriptor) – The considered arc.
Returns:: The vertex descriptor of the source of e.

target(e: EdgeDescriptor) → int[source]#

Retrieves the target vertex of an arc in this Graph instance.

Parameters:: e (EdgeDescriptor) – The considered arc.
Returns:: The vertex descriptor of the target of e.

to_dot(**kwargs) → str[source]#

Exports this Graph instance to a Graphviz string. See the to_dot() function.

Returns:: The corresponding graphviz string.

vertices() → iter[source]#

Gets an iterator over the vertices involved in this Graph instance.

Returns:: An iterator over the vertices.

class UndirectedGraph(num_vertices: int = 0)[source]#

Bases: Graph

The UndirectedGraph models a undirected graph. As it is undirected the reverse edge are automatically added/inserted.

pybgl.graph_copy module#

class DepthFirstSearchCopyVisitor(g_dup: Graph, pmap_vrelevant: ReadPropertyMap, pmap_erelevant: ReadPropertyMap, pmap_vertices: ReadWritePropertyMap, pmap_edges: ReadWritePropertyMap, pmap_vcolor: ReadWritePropertyMap, callback_dup_vertex: callable = None, callback_dup_edge: callable = None)[source]#

Bases: DepthFirstSearchExtractVisitor

The DepthFirstSearchCopyVisitor implements the graph_copy() function.

Constructor.

Parameters:

g_dup – Pass an empty graph.
pmap_vrelevant (ReadPropertyMap) – A ReadPropertyMap{VertexDescriptor: bool} which indicates for each vertex whether if it must be duped or not.
pmap_erelevant (ReadPropertyMap) – A ReadPropertyMap{EdgeDescriptor: bool} which indicates for each edge whether it is relevant or not.
pmap_vertices (ReadWritePropertyMap) – A ReadWritePropertyMap{VertexDescriptor: VertexDescriptor} which maps each vertex of g to the corresponding vertex in g_copy. Pass an empty property map.
pmap_edges (ReadWritePropertyMap) – A ReadWritePropertyMap{EdgeDescriptor: EdgeDescriptor} which maps each edge of g with the corresponding edge in g_copy. Pass None if unused, otherwise, pass an empty property map.
pmap_vcolor (ReadWritePropertyMap) – A ReadWritePropertyMap{VertexDescriptor: Color} which maps each vertex with its status in the DFS walk. Pass an empty property map. See depth_first_search() for further details.
callback_dup_vertex – A Callback(u, g, u_dup, g_dup) where: u is the original VertexDescriptor (in g); g is the original DirectedGraph; u_dup is the duplicated VertexDescriptor (in g_dup); g_dup is the duplicated DirectedGraph.; Pass None if unused.
callback_dup_edge – A Callback(e, g, e_dup, g_dup) where: e is the original EdgeDescriptor (in g); g is the original DirectedGraph; e_dup is the duplicated EdgeDescriptor (in g_dup); g_dup is the duplicated DirectedGraph.; Pass None if unused.

dup_vertex(u: int, g: Graph) → int[source]#

Implementation method, used to duplicate a vertex.

Parameters:

u (int) – The vertex descriptor of the duplicated node.
g (Graph) – The input graph.

examine_relevant_edge(e: EdgeDescriptor, g: Graph)[source]#

Method triggered when discovering a relevant edge not yet visited.

Parameters:

e (EdgeDescriptor) – The discovered edge.
g (Graph) – The considered graph.

start_vertex(s: int, g: Graph)[source]#

Method invoked on the source vertex once before the start of the search.

Parameters:

s (int) – The source vertex.
g (Graph) – The considered graph.

graph_copy(s: int, g: Graph, g_dup: Graph, pmap_vrelevant: ReadPropertyMap = None, pmap_erelevant: ReadPropertyMap = None, pmap_vertices: ReadWritePropertyMap = None, pmap_edges: ReadWritePropertyMap = None, callback_dup_vertex: callable = None, callback_dup_edge: callable = None)[source]#

Copies a sub-graph from a Graph according to an edge-based filtering starting from a given source node.

Parameters:

s – The VertexDescriptor of the source node.
g – A Graph instance.
pmap_vrelevant (ReadPropertyMap) – A ReadPropertyMap{VertexDescriptor: bool} which indicates for each vertex whether if it must be duped or not. Only relevant if vis == None.
pmap_erelevant (ReadPropertyMap) – A ReadPropertyMap{EdgeDescriptor: bool} which indicates for each edge whether if it must be duped or not. Only used if vis == None.
callback_dup_vertex (callable) – A Callback(u, g, u_dup, g_dup). Pass None if irrelevant.
callback_dup_edge (callable) – A Callback(e, g, e_dup, g_dup). Pass None if irrelevant.

pybgl.graph_dp module#

class GraphDp(g: Graph, dpv: dict = None, dpe: dict = None, dg: dict = None, dv: dict = None, de: dict = None, extra_style: list = None)[source]#

Bases: object

Graph dynamic properties, used to define the style of a graph. It allows to render graph to GraphViz.

Constructor.

Parameters:

g (Graph) – The wrapped graph.
dpv (dict) – Per-vertex style. It maps a vertex Graphviz attribute with the corresponding vertex-based ReadPropertyMap instance.
dpe (dict) – Per-edge style. It maps a edge Graphviz attribute with the corresponding edge-based ReadPropertyMap instance.
dg (dict) – Graph attributes.
dv (dict) – Default vertex style. It maps a vertex Graphviz attribute with the corresponding value.
de (dict) – Default edge style. It maps a edge Graphviz attribute with the corresponding value.
extra_style (list) – Extra style (splines, etc).

get_de() → dict[source]#

get_dg() → dict[source]#

get_dpe() → dict[source]#

get_dpv() → dict[source]#

get_dv() → dict[source]#

to_dot(**kwargs) → str[source]#

Exports this GraphDp instance to the corresponding GraphViz string.

Returns:: The corresponding GraphViz string.

to_json(vs: iter = None, es: iter = None) → str[source]#

Exports the GraphViz rendering of this GraphDp instance to JSON.

Parameters:

vs (iter) – A subset of vertices of self.g. You should rather use the GraphView class.
es (iter) – A subset of edges of self.g. You should rather use the GraphView class.

Returns:

The corresponding JSON string.

pybgl.graph_extract module#

class DepthFirstSearchExtractVisitor(pmap_vrelevant: ReadPropertyMap, pmap_erelevant: ReadPropertyMap, pmap_vcolor: ReadWritePropertyMap, callback_vertex_extract: callable = None, callback_edge_extract: callable = None)[source]#

Bases: DefaultDepthFirstSearchVisitor

The DepthFirstSearchExtractVisitor limits the DFS walk to traverse only relevant arcs.

See also the DepthFirstSearchCopyVisitor class.

Constructor.

Parameters:

pmap_vrelevant (ReadPropertyMap) – A ReadPropertyMap{VertexDescriptor: bool} which indicates for each vertex whether if it must be duped or not. You shoud consider the GraphView class.
pmap_erelevant (ReadPropertyMap) – A ReadPropertyMap{EdgeDescriptor: bool} which indicates for each edge whether it is relevant or not. You shoud consider the GraphView class.
pmap_vcolor (ReadWritePropertyMap) – A ReadWritePropertyMap{VertexDescriptor: Color} which maps each vertex with its status in the DFS walk. See the depth_first_search() function.
callback_vertex_extract (callable) – Callback triggered when discovering a vertex to extract.
callback_edge_extract (callable) – Callback triggered when discovering an edge to extract.

discover_vertex(u: int, g: Graph)[source]#

Method invoked when the DFS discover a relevant vertex not yet visited.

Parameters:

u (int) – The discovered vertex.
g (Graph) – The considered graph.

examine_edge(e: EdgeDescriptor, g: Graph)[source]#

Method invoked when the DFS discover a vertex not yet visited.

Parameters:

e (EdgeDescriptor) – The discovered edge.
g (Graph) – The considered graph.

examine_relevant_edge(e: EdgeDescriptor, g: Graph)[source]#

Method triggered when discovering a relevant edge not yet visited.

Parameters:

e (EdgeDescriptor) – The discovered edge.
g (Graph) – The considered graph.

graph_extract(s: int, g: Graph, pmap_vrelevant: ReadPropertyMap = None, pmap_erelevant: ReadPropertyMap = None, callback_vertex_extract: callable = None, callback_edge_extract: callable = None)[source]#

Extract the edges of a given Graph according to an edge-based filtering starting from a given source node.

Parameters:

s – The VertexDescriptor of the source node.
g – A Graph instance.
pmap_vrelevant (ReadPropertyMap) – A ReadPropertyMap{VertexDescriptor: bool} which indicates for each vertex whether if it must be duped or not. You shoud consider the GraphView class.
pmap_erelevant (ReadPropertyMap) – A ReadPropertyMap{EdgeDescriptor: bool} which indicates each edge of the Graph with a boolean equal to True iff the edge is relevant. You shoud consider the GraphView class.
callback_vertex_extract (callable) – Callback triggered when discovering a vertex to extract.
callback_edge_extract (callable) – Callback triggered when discovering an edge to extract.

pybgl.graph_traversal module#

class DefaultTreeTraversalVisitor[source]#

Bases: object

discover_vertex(u: int, g: Graph)[source]#

Method invoked when a vertex is encountered for the first time.

Parameters:

u (int) – The vertex being discovered.
g (Graph) – The considered tree.

examine_edge(e: EdgeDescriptor, g: Graph)[source]#

Method invoked on every out-edge of each vertex after it is discovered.

Parameters:

e (EdgeDescriptor) – The edge being examined.
g (Graph) – The considered tree.

finish_vertex(u: int, g: Graph)[source]#

Method invoked on a vertex after all of its out edges have been added to the search tree and all of the adjacent vertices have been discovered (but before their out-edges have been examined).

Parameters:

u (int) – The vertex being finished.
g (Graph) – The considered tree.

start_vertex(s: int, g: Graph)[source]#

Method invoked on the source vertex once before the start of the search.

Parameters:

s (int) – The source vertex.
g (Graph) – The considered tree.

bfs_tree(s: int, g: Graph, vis: DefaultTreeTraversalVisitor = None)[source]#

Simplified implementation Breadth First Search algorithm for trees See also breadth_first_search().

Parameters:

s (int) – The vertex descriptor of the source.
g (Graph) – The graph being explored.
vis (DefaultTreeTraversalVisitor) – An optional visitor.

dfs_tree(s: int, g: Graph, vis: DefaultTreeTraversalVisitor = None)[source]#

Simplified implementation Depth First Search algorithm for trees See also depth_first_search().

Parameters:

s (int) – The vertex descriptor of the source.
g (Graph) – The graph being explored.
vis (DefaultTreeTraversalVisitor) – An optional visitor.

pybgl.graph_view module#

class GraphView(g: Graph, pmap_vrelevant: ReadPropertyMap = None, pmap_erelevant: ReadPropertyMap = None)[source]#

Bases: object

The GraphView allows to iterate on a subset of vertices and edges of a Graph instance, according to arbitary property maps.

You may combine multiple GraphView instances using logical operators (e.g., &, |, -).

Constructor.

Parameters:

g (Graph) – A graph instance.
pmap_vrelevant (ReadPropertyMap) – A read property map which maps each vertex with a boolean indicating whether the considered vertex is relevant.
pmap_erelevant (ReadPropertyMap) – A read property map which maps each edge with a boolean indicating whether the considered vertex is relevant.

edges() → iter[source]#

Gets an iterator over the relevant edges of the nested Graph instance.

Returns:: An iterator over the relevant edges.

in_degree(u: int) → int[source]#

Gets the in-degree (the number of out-edges) of a vertex u involved in this GraphView instance.

Raises:: RuntimeError – Raised if self.g does not expose an in_edges method.
Parameters:: u (int) – The considered vertex.
Returns:: The out-degree of u

in_edges(u: int) → iter[source]#

Gets an iterator over the relevant in-edges of a given vertex of the nested IncidenceGraph instance.

Raises:: RuntimeError – Raised if self.g does not expose an in_edges method.
Parameters:: u (int) – The considered vertex.
Returns:: An iterator over the relevant in-edges.

num_edges() → int[source]#

Counts the number of relevant edges involved in this GraphView instance.

Returns:: The number of edges.

num_vertices() → int[source]#

Counts the number of relevant vertices involved in this GraphView instance.

Returns:: The number of vertices.

out_degree(u: int) → int[source]#

Gets the out-degree (the number of out-edges) of a vertex u involved in this GraphView instance.

Parameters:: u (int) – The considered vertex.
Returns:: The out-degree of u

out_edges(u: int) → iter[source]#

Gets an iterator over the relevant out-edges of a given vertex of the nested Graph instance.

Parameters:: u (int) – The considered vertex.
Returns:: An iterator over the relevant out-edges.

to_dot(*cls, **kwargs) → str[source]#

Exports this GraphView instance to a Graphviz string. See the to_dot() function.

Returns:: The corresponding graphviz string.

vertices() → iter[source]#

Gets an iterator over the relevant vertices of the nested Graph instance.

Returns:: An iterator over the relevant vertices.

pybgl.graphviz module#

class GraphvizOptsParser[source]#

Bases: HTMLParser

The GraphvizOptsVisitor is used to parse HTML content related to a vertex or an edge.

Constructor.

feed(graphviz_opts)[source]#

Feed data to the parser.

Call this as often as you want, with as little or as much text as you want (may include ‘n’).

handle_starttag(tag, attrs)[source]#

items()[source]#

class GraphvizVisitor[source]#

Bases: object

The GraphvizVisitor is the base of the ReadGraphvizVisitor class.

on_edge(line: str, u: int, v: int, g: Graph, opts: str)[source]#

on_else(line: str)[source]#

on_vertex(line: str, u: int, g: Graph, opts: str)[source]#

class ReadGraphvizDpVisitor(g, dpv: dict, dpe: dict)[source]#

Bases: ReadGraphvizVisitor

The ReadGraphvizDpVisitor is used to implement the read_graphviz_dp() function. It is used to initialize a Graph instance from a Graphviz file.

Constructor.

on_install_edge_property(e, g, key, value)[source]#

on_install_vertex_property(u, g, key, value)[source]#

class ReadGraphvizVisitor[source]#

Bases: GraphvizVisitor

The ReadGraphvizVisitor is used to implement the read_graphviz() function. It is used to initialize a Graph instance from a Graphviz file.

Constructor.

on_edge(line: str, u_alias: int, v_alias: int, g: Graph, opts: str) → EdgeDescriptor[source]#

on_install_edge_property(e, g, key, value)[source]#

on_install_vertex_property(u, g, key, value)[source]#

on_vertex(line: str, u_alias: int, g: Graph, opts: str) → int[source]#

dot_to_svg(s_dot: str, engine: str = 'dot', format: str = 'svg') → str[source]#

Converts a Graphviz string to SVG.

Parameters:

s_dot (str) – A string in the graphviz format.
engine (str) – The graphviz engine used for the rendering. See “man dot” for more details. Valid values: (e.g., "dot", "fdp", "neato", …). You may also pass None to use the default engine ("dot").
format (str) – The output graphviz terminal, e.g. "svg", "png". See man dot for more details.

Returns:

The corresponding SVG string.

dotstr_to_html(s_dot: str, engine: str = 'dot') → str[source]#

Converts a Graphviz string to a HTML string.

Parameters:

s_dot (str) – A string in the graphviz format.
engine (str) – The graphviz engine used for the rendering. See “man dot” for more details. Valid values: (e.g., "dot", "fdp", "neato", …). You may also pass None to use the default engine ("dot").

Returns:

The corresponding HTML string.

error(*cls)[source]#: Prints an error message.

graph_to_html(g, engine: str = None, **kwargs) → str[source]#

Converts a graph to a HTML string.

Parameters:

g (Graph) – The input graph.
**kwargs (dict) – See the Graph.to_dot() method.

Returns:

The corresponding HTML string.

read_graphviz(iterable, g: Graph, vis: ReadGraphvizVisitor = None)[source]#

Read an iterable where each element is a line of a graphviz string to extract a graph, but not its attributes. See read_graphviz_dp if needed. This function expect at most one vertex per line and one edge per line.

Assumptions:

The vertices are identified using integer
The vertices are described in the dot file before the edges
The vertex/edge attributes are not too weird strings

See the read_graphviz_dp() function to load Graphviz styles.

Parameters:

iterable – The input Graphviz lines (e.g., my_file.readlines() or my_str.splitlines())
g (Graph) – Pass an empty DirectedGraph or UndirectedGraph instance.

read_graphviz_dp(iterable: iter, g: Graph, dpv: dict = None, dpe: dict = None)[source]#

Read an iterable where each element is a line of a graphviz string to extract a graph and its node/edge attributes. This function expect at most one vertex per line and one edge per line.

Parameters:

iterable – An iterable (e.g., my_file.readlines() or my_str.splitlines())
g (DirectedGraph) – Pass an empty graph.
dpv (dict) – Pass an empty dict if needed. It will map for each vertex a dict mapping each specified graphviz attributes with its value.
dpe (dict) – Pass an empty dict if needed. It will map for each edge a dict mapping each specified graphviz attributes with its value.

run_graphviz(s_dot: str, engine: str = None, format: str = 'svg') → bytes[source]#

Converts a dot string (graphviz format) into a graphic file.

Parameters:

s_dot (str) – A string in the graphviz format.
engine (str) – The graphviz engine used for the rendering. See “man dot” for more details. Valid values: (e.g., "dot", "fdp", "neato", …). You may also pass None to use the default engine ("dot").
format (str) – The output graphviz terminal, e.g. "svg", "png". See man dot for more details.

Returns:

The bytes/str of the output image iff successful, None otherwise.

write_graphviz(s_dot: str, filename: str, engine: str = 'dot', format: str = 'svg') → bool[source]#

Writes a dot string (Graphviz format) into a graphic file.

Parameters:

s_dot (str) – A string in the graphviz format.
filename (str) – The path of the output file.
engine (str) – The graphviz engine used for the rendering. See “man dot” for more details. Valid values: (e.g., "dot", "fdp", "neato", …). You may also pass None to use the default engine ("dot").
format (str) – The output graphviz terminal, e.g. "svg", "png". See man dot for more details.

Returns:

True iff successful.

pybgl.graphviz_impl module#

class EscapeHtmlTokenizeVisitor[source]#

Bases: TokenizeVisitor

Internal class used by the graphviz_escape_html() function.

on_matched(matched: str, start: int, end: int, s: str)[source]#

Method invoked when a substring has been catched by any pattern of the tokenizer.

Parameters:

unmatched (str) – The matched substring.
start (int) – The starting index of the matched string in the original string.
end (int) – The ending index of the matched string in the original string.
s (str) – The original string.

on_unmatched(unmatched: str, start: int, end: int, s: str)[source]#

Method invoked when a substring has not been catched by any pattern of the tokenizer.

Parameters:

unmatched (str) – The unmatched substring.
start (int) – The starting index of the unmatched string in the original string.
end (int) – The ending index of the unmatched string in the original string.
s (str) – The original string.

class GraphvizStyle(*args, **kwargs)[source]#

Bases: object

The GraphvizStyle class is a singleton that configure the default style used to render PyBGL graphs in a Jupyter notebook.

It is useful if you want graph adapted e.g. for dark themes.

Example

>>> from pybgl.graph import (
...     DirectedGraph, GraphvizStyle, ipynb_display_graph
... )
>>> GraphvizStyle.set_fg_color("grey")
>>> GraphvizStyle.set_bg_color("transparent")
>>> display_graph = ipynb_display_graph
>>> g = DirectedGraph(2)
>>> g.add_edge(0, 1)
>>> display_graph(g)

static attributes_to_dot(prefix: str, d: dict) → str[source]#

Internal method, used to convert this GraphvizStyle attribute to Graphviz attributes.

Parameters:

prefix (str) – A string in "graph", "node", "edge".
d (dict) – The prefix-related style attributes.

Returns:

The corresponding Graphviz string.

edge = {'color': 'black', 'fontcolor': 'black'}#

extra_style = []#

graph = {'bgcolor': 'transparent', 'fontcolor': 'black', 'rankdir': 'LR'}#

node = {'color': 'black', 'fillcolor': 'transparent', 'fontcolor': 'black', 'shape': 'circle'}#

static set_bg_color(color)[source]#

Sets the background color used to render graphs.

Parameters:: color (str) – A graphviz color. If you want to use HTML color, see html_to_graphviz().

static set_fg_color(color: str)[source]#

Sets the foreground color used to render graphs.

Parameters:: color (str) – A graphviz color. If you want to use HTML color, see html_to_graphviz().

default_graphviz_style() → str[source]#

Crafts the default Graphviz string corresponding to the default style used to render a graph.

Returns:: The corresponding Graphviz string.

edge_to_graphviz(e, g, dpe: dict = None, vertex_to_str: callable = None) → str[source]#

Exports a edge as well as its style properties to Graphviz.

Parameters:

e (int) – The considered edge.
g (Graph) – The considered graph.
dpe (dict) – The edge-based style. See also GraphDp class.
vertex_to_str (callable) – A function used to convert a vertex descriptor to the corresponding Graphviz vertex identifier. This is useful if the vertex descriptor is more sophisticated than an int (e.g., a tuple).

Returns:

The corresponding Graphviz string.

enrich_kwargs(default_d: dict, key: str, **kwargs) → dict[source]#

Add a key value pair in a dictionnary involved in the values of **kwargs. This function is commonly used in the methods that inherit the Graph.to_dot method to complete the Graphviz style. See for example the the Automaton.to_dot method.

Parameters:

default_d (dict) – The source dictionnary, containing the key value pairs used to complete **kwargs.
key (dict) – The key of **kwargs to update.

Returns:

The updated **kwargs.

graphviz_arc(g) → str[source]#

Returns the appropriate string for directed/undirected edge declarations in Graphviz.

Returns:: "->" if the graph is directed, "--" otherwise.

graphviz_dx_to_dot(prefix: str, dx: dict) → str[source]#

graphviz_escape_char(a: str) → str[source]#

Escapes a character that must be involved in a Graphviz string.

Parameters:: a (str) – A (possibly special) character.
Returns:: The corresponding escaped character for Graphviz.

graphviz_escape_html(s: str) → str[source]#

Escapes a string that must be involved in a Graphviz string.

Parameters:: s (str) – A string involving possibly special characters.
Returns:: The corresponding escaped string for Graphviz.

graphviz_properties_to_str(x: object, dpx: dict) → str[source]#

Internal method, used to exports a vertex or an edge as well at its style to the corresponding Graphviz string. See the vertex_to_graphviz() and edge_to_graphviz() functions.

Parameters:

x (object) – The vertex or the edge to be exported.
dpx (dict) – The corresponding style. See also GraphDp class.

Returns:

The resulting Graphviz string.

graphviz_type(g) → str[source]#

Returns the appropriate string for directed/undirected graph declarations in Graphviz.

Returns:: "digraph" if the graph is directed, "graph" otherwise.

to_dot(g, vs: iter = None, es: iter = None, dg: dict = None, extra_style: str = None, dv: dict = None, de: dict = None, dpv: dict = None, dpe: dict = None, graphviz_style: str = None, vertex_to_str: callable = None) → str[source]#

Internal method, used for Graphviz rendering. Exports a graph to its corresponding Graphviz string. See also GraphDp.

Parameters:

g (Graph) – The graph to be rendered.
vs (iter) – A subset of vertices of g. If you pass None, iterates over all the vertices. Use rather GraphView.
es (iter) – A subset of edges of g. If you pass None, iterates over all the edges. Use rather GraphView.
dpv (dict) – Per-vertex style. It maps a vertex Graphviz attribute with the corresponding vertex-based ReadPropertyMap instance.
dpe (dict) – Per-edge style. It maps a edge Graphviz attribute with the corresponding edge-based ReadPropertyMap instance.
dg (dict) – Graph attributes.
dv (dict) – Default vertex style. It maps a vertex Graphviz attribute with the corresponding value.
de (dict) – Default edge style. It maps a edge Graphviz attribute with the corresponding value.
graphviz_style (list) – Extra style (splines, etc).
vertex_to_str (callable) – A function used to convert a vertex descriptor to the corresponding Graphviz vertex identifier. This is useful if the vertex descriptor is more sophisticated than an int (e.g., a tuple).

Returns:

The corresponding Graphviz string.

vertex_to_graphviz(u: int, g, dpv: dict = None, vertex_to_str: callable = None) → str[source]#

Exports a vertex as well as its style properties to Graphviz.

Parameters:

u (int) – The considered vertex.
g (Graph) – The considered graph.
dpv (dict) – The vertex-based style. See also GraphDp class.
vertex_to_str (callable) – A function used to convert a vertex descriptor to the corresponding Graphviz vertex identifier. This is useful if the vertex descriptor is more sophisticated than an int (e.g., a tuple).

Returns:

The corresponding Graphviz string.

pybgl.heap module#

class Comparable(obj: object, preorder: callable = None)[source]#

Bases: object

Wrapper used to define a custom pre-order for a given object.

This class is inspired from functools.cmp_to_key and this discussion. The objects to be sorted are wrapped in an instance that implements the < operator called by the sorting function.

Constructor.

Example

>>> x = Comparable(5, lambda a, b: a >= b)

Parameters:

obj – An Element instance.
preorder – A callable acting as a preorder.

class Heap(elements: iter = None, to_comparable: callable = None)[source]#

Bases: object

The Heap class implements a heap using an arbitrary preorder. It answers the limitation of :py:func:heappop and heappush() which assume that the heap is ordered according to <=.

Constructor.

Example

>>> heap = Heap(
...     [4, 2, 2, 1, 3],
...     to_comparable=lambda x: Comparable(x, lambda a, b: a >= b)
... )
>>> heap
Heap([4, 3, 2, 2, 1])

Parameters:

elements (iter) – The elements used to initialize this Heap instance.
to_comparable (callable) – A callable used to define the preorder used to sort elements pushed in this Heap instance.

decrease_key(element: object)[source]#

pop() → tuple[source]#

Pops an element to this Heap instance.

Returns:: The popped element.

push(element: object)[source]#

Pushes an element to this Heap instance.

Parameters:: element (object) – The object to be pushed.

compare_to_key(preorder: callable)[source]#

Convert a preorder to a key callback (used, e.g., by the sorted() function).

Example

>>> key = compare_to_key(lambda a, b: a >= b)

Parameters:: preorder – A callable(Element, Element) that is preorder over the space of Elements.

pybgl.hopcroft_minimize module#

hopcroft_agglomerate_states(g: IncidenceAutomaton) → set[source]#

Initialization step of the Hopcroft minimization algorithm.

Parameters:: g (IncidenceAutomaton) – The input automaton.
Returns:: A set of frozensets, where each of them corresponds to a group of agglomerated states.

hopcroft_minimize(g: IncidenceAutomaton) → IncidenceAutomaton[source]#

Runs the Hopcroft minimization algorithm.

Parameters:: g (IncidenceAutomaton) – The input automaton.
Returns:: The minimized automaton.

pybgl.html module#

beside(contents1: str, contents2: str, title: str = '', title1: str = '', title2: str = '') → str[source]#

Exports two HTML contents so that they are displayed beside.

Parameters:

contents1 (str) – A string containing the content displayed on the right.
contents2 (str) – A string containing the content displayed on the left.
title (str) – A string containing the title of the figure.
title1 (str) – A string containing the caption of the left content.
title2 (str) – A string containing the caption of the right content.

Returns:

The corresponding HTML str instance.

html(s: str)[source]#

Evaluates HTML code in a Jupyter Notebook.

Parameters:: s – A str containing HTML code.

pybgl.incidence_automaton module#

class IncidenceAutomaton(*args, **kwargs)[source]#

Bases: Automaton

The IncidenceAutomaton extends the Automaton so that the IncidenceAutomaton.in_edges() and the IncidenceAutomaton.in_degree() are well-defined. This is done by mapping each state with its input transitions.

Constructor.

:param See Automaton.__init__().:

add_edge(q: int, r: int, a: str) → tuple[source]#

Adds a transition to this Automaton instance.

Parameters:

q (int) – The vertex descriptor of source state of the new transition.
r (int) – The vertex descriptor of target state of the new transition.
a (str) – The label of the new transition.

Returns:

A tuple (e, success) where e is an EdgeDescriptor compliant with this Automaton class and success == True if successful, (None, False) otherwise.

add_vertex() → int[source]#

Adds a vertex to this Graph instance.

Returns:: The vertex descriptor of the added vertex.

in_edges(r: int)[source]#

Retrieves an iterator over the in-edges of a state q involved in this Automaton instance.

Parameters:: q (int) – The target vertex.

:raises RuntimeError` as a Automaton must no: :raises support this primitive. If you require it, use the: :raises IncidenceAutomaton:

Returns:: An iterator over the edges of q.

remove_edge(e: EdgeDescriptor)[source]#

Removes a transition from this Automaton instance.

Parameters:: e (EdgeDescriptor) – The edge descriptor of the transition to be removed.

remove_vertex(q: int)[source]#

Removes a vertex from this Graph instance.

Parameters:: u (int) – The vertex descriptor of the vertex to be removed.
Raises:: KeyError –

make_incidence_automaton(transitions: list, q0n: int = 0, pmap_vfinal: ReadPropertyMap = None) → IncidenceAutomaton[source]#

Builds an IncidenceAutomaton instance according to a set of edges, by specializing make_automaton().

See make_automaton() for additional details.

Returns:: The corresponding IncidenceAutomaton instance.

pybgl.incidence_graph module#

class IncidenceGraph(num_vertices: int = 0)[source]#

Bases: DirectedGraph

The IncidenceGraph extends the DirectedGraph so that the IncidenceGraph.in_edges() and the IncidenceGraph.in_degree() are well-defined. This is done by mapping each state with its input transitions.

Constructor.

:param See Graph.__init__().:

add_edge(u: int, v: int) → tuple[source]#

Adds an edge to this Graph instance.

Parameters:

u (int) – The vertex descriptor of source vertex of the new edge.
v (int) – The vertex descriptor of target vertex of the new edge.

Returns:

A tuple (e, success) where e is an EdgeDescriptor compliant with this Graph class and success == True if successful, (None, False) otherwise.

add_vertex() → int[source]#

Adds a vertex to this Graph instance.

Returns:: The vertex descriptor of the added vertex.

in_edges(v: int)[source]#

Gets an iterator over the in-edges of a vertex v involved in this Graph instance.

Parameters:: v (int) – The target vertex.
Returns:: An iterator over the out-edges of v.

remove_edge(e: EdgeDescriptor)[source]#

Removes an edge from this Graph instance.

Parameters:: e (EdgeDescriptor) – The edge descriptor of the edge to be removed.

remove_vertex(u: int)[source]#

Removes a vertex from this Graph instance.

Parameters:: u (int) – The vertex descriptor of the vertex to be removed.
Raises:: KeyError –

pybgl.incidence_node_automaton module#

class IncidenceNodeAutomaton(*args, pmap_vsymbol: ReadPropertyMap = None, **kwargs)[source]#

Bases: NodeAutomaton

Constructor.

Parameters:: pmap_vsymbol (ReadPropertyMap) – A property map which maps each state with its corresponding symbol.

add_edge(q: int, r: int) → tuple[source]#

Adds a transition to this NodeAutomaton instance.

Parameters:

q (int) – The vertex descriptor of source state of the new transition.
r (int) – The vertex descriptor of target state of the new transition.
a (str) – The label of the new transition.

Returns:

A tuple (e, success) where e is an EdgeDescriptor compliant with this Automaton class and success == True if successful, (None, False) otherwise.

in_edges(r: int)[source]#

Retrieves an iterator over the in-edges of a state q involved in this Automaton instance.

Parameters:: q (int) – The target vertex.

:raises RuntimeError` as a Automaton must no: :raises support this primitive. If you require it, use the: :raises IncidenceAutomaton:

Returns:: An iterator over the edges of q.

remove_edge(e: EdgeDescriptor)[source]#

Removes a transition from this NodeAutomaton instance.

Parameters:: e (EdgeDescriptor) – The edge descriptor of the transition to be removed.

remove_vertex(q: int)[source]#

Removes a vertex from this Graph instance.

Parameters:: u (int) – The vertex descriptor of the vertex to be removed.
Raises:: KeyError –

make_incidence_node_automaton(transitions: list, pmap_vlabel: ~pybgl.property_map.ReadPropertyMap = None, q0n: int = 0, pmap_vfinal: ~pybgl.property_map.ReadPropertyMap = None, Constructor=<class 'pybgl.incidence_node_automaton.IncidenceNodeAutomaton'>) → IncidenceNodeAutomaton[source]#

Specialization of the make_node_automaton() function for the IncidenceNodeAutomaton class.

Parameters:

transitions (list) – The list of transitions, where is each transition is modeled by a (qn, rn, a) tuple and where qn identifies the source of the transition rn identifies the target of the transition and a labels the transition.
pmap_vlabel (ReadPropertyMap) – A property map which maps each state identifier with its corresponding symbol.
q0n (int) – The identifier in transitions of the initial state.
pmap_vfinal (ReadPropertyMap) – A property map which maps each state identifier with a boolean indicating whether the state is final (True) or not (False).
Constructor – The class use to allocate the automaton. Defaults to IncidenceNodeAutomaton.

Example

>>> from collections import defaultdict
>>> from pybgl import (
...    Automaton, make_assoc_property_map,
...    make_incidence_node_automaton
... )
>>> transitions = [("root", "sink"), ("root", "sink")]
>>> map_vlabel = defaultdict(bool, {"root": "a", "sink": "b"})
>>> map_vfinal = defaultdict(bool, {"root": False, "sink": True})
>>> g = make_incidence_node_automaton(
...     transitions,
...     q0n="root",
...     pmap_vlabel=make_assoc_property_map(map_vlabel),
...     pmap_vfinal=make_assoc_property_map(map_vfinal)
... )

Returns:: The corresponding IncidenceNodeAutomaton instance.

pybgl.ipynb module#

background_template_html(background_color: str = None) → str[source]#

Crafts an HTML template to nest HTML code in a div setting the background to a given color.

Example

>>> from pybgl import (
...     DirectedGraph, html, background_template_html, graph_to_html
... )
>>> g = DirectedGraph(2)
>>> g.add_edge(0, 1)
>>> html(background_template_html("white") % graph_to_html(g))

Parameters:: background_color (str) – An HTML color.
Returns:: The corresponding HTML template.

display_body(body_html: str, filename_html: str, background_color: str = None) → str[source]#

Wraps HTML content in an HTML body tag.

Parameters:

body_html (str) – The HTML content.
filename_html (str) – The path of the HTML file in which body_html will be dumped.
background_color (str) – An HTML color or None if not needed.

display_svg(svg, filename_svg: str, background_color: str = None)[source]#

Writes SVG content into and display it in a Jupyter Notebook with an HTML link. This is useful is the graph is too large to be readable in Jupyter. See also the display_body() function if the generated HTML must be standalone.

Parameters:

svg (str) – The SVG content.
filename_svg (str) – The path to the SVG file in which svg to be dumped.
background_color (str) – An HTML color or None if not needed.

Example

>>> from pybgl import (
...     DirectedGraph, html, background_template_html, graph_to_html
... )
>>> g = DirectedGraph(2)
>>> g.add_edge(0, 1)
>>> display_svg(graph_to_html(g), "g.svg", background_color="white")

in_ipynb() → bool[source]#

Tests whether the code is running inside a Jupyter Notebook.

Returns:: True iff the code is running inside a Jupyter Notebook.

ipynb_display_graph(g, background_color: str = None, **kwargs)[source]#

Displays a Graph in a Jupyter Notebook. If the graph is large, see the display_svg() function instead.

Parameters:

g (Graph) – The graph to display
background_color (str) – An HTML color.
**kwargs (dict) – See the Graph.to_dot() method.

pybgl.lcs_distance module#

class LcsDistance(x: str, y: str)[source]#

Bases: object

The LcsDistance class is used to implement the memoization used by the lcs_distance() function.

Constructor.

Parameters:

x (str) – The left operand.
y (str) – The right operand.

compute(i: int = 0, j: int = 0) → int[source]#

Computes the LCS (Longest Common Substring) distance, with memoization.

Parameters:

i (int) – The current index in self.x.
j (int) – The current index in self.y.

Returns:

The minimal number of insertion/deletion operations needed to transform x into y.

lcs_distance(x: str, y: str) → int[source]#

Computes the LCS (Longest Common Substring) distance, with memoization.

Parameters:

x (str) – The left operand.
y (str) – The right operand.

Returns:

The minimal number of insertion/deletion substitution operations needed to transform x into y.

lcs_distance_naive(x: str, y: str) → int[source]#

Inefficient implementation of the LCS (Longest Common Substring) distance (no memoization).

Parameters:

x (str) – The left operand.
y (str) – The right operand.

Returns:

The minimal number of insertion/deletion operations needed to transform x into y.

pybgl.levenshtein_distance module#

class LevenshteinDistance(x: str, y: str)[source]#

Bases: object

The LevenshteinDistance class is used to implement the memoization used by the levenshtein_distance() function.

Constructor.

Parameters:

x (str) – The left operand.
y (str) – The right operand.

compute(i: int = 0, j: int = 0) → int[source]#

Computes the Levenshtein distance, with memoization.

Parameters:

i (int) – The current index in self.x.
j (int) – The current index in self.y.

Returns:

The minimal number of insertion/deletion/substitution operations needed to transform x into y.

levenshtein_distance(x: str, y: str) → int[source]#

Computes the Levenshtein distance, with memoization.

Parameters:

x (str) – The left operand.
y (str) – The right operand.

Returns:

The minimal number of insertion/deletion/substitution operations needed to transform x into y.

levenshtein_distance_naive(x: str, y: str) → int[source]#

Inefficient implementation of the Levenshtein distance (no memoization). Prefer the levenshtein_distance() function.

Parameters:

x (str) – The left operand.
y (str) – The right operand.

Returns:

The minimal number of insertion/deletion/substitution operations needed to transform x into y.

pybgl.moore_determination module#

moore_determination(nfa: Nfa, dfa: Automaton = None, complete: bool = True) → Automaton[source]#

Converts the input NFA into a DFA. The output DFA has a state for every reachable subset of states in the input NFA. In the worst case, there will be an exponential increase in the number of states. Adapted from this script <https://viterbi-web.usc.edu/~breichar/teaching/2011cs360/NFAtoDFA.py>.

Parameters:

nfa (Nfa) – An Nfa instance.
dfa (Automaton) – Pass None or a reference to an empty Automaton instance.
complete (bool) – Pass True to build the complete automaton (original algorithm). Pass False to build a smaller automaton (this saves the “trash” state and its corresponding input transitions).

Returns:

The corresponding Automaton instance.

pybgl.nfa module#

class Nfa(num_vertices: int = 0, initials: set = None, pmap_vfinal: ReadWritePropertyMap = None, epsilon: str = 'ε')[source]#

Bases: DirectedGraph

The Nfa implements a Non-deterministic Finite Automaton.

Constructor.

Parameters:

num_vertices (int) – Pass the (initial) number of vertices.
initials (str) – The vertex descriptors of the initial states.
pmap_vfinal (ReadPropertyMap) – A ReadPropertyMap that maps a vertex descriptor with a boolean which equals True if the vertex is a final state None otherwise.
epsilon (str) – The symbol assigned to the epsilon-transition.

accepts(w: str) → True[source]#

Tests whether this Nfa instance accepts a word, meaning there exist a state reached from its initial state by consuming successively each character of the input word.

Parameters:: w (str) – The input word.
Returns:: True if the automaton accepts w False otherwise.

add_edge(q: int, r: int, a: str) → tuple[source]#

Adds a transition to this Nfa instance.

Parameters:

q (int) – The vertex descriptor of source state of the new transition.
r (int) – The vertex descriptor of target state of the new transition.
a (str) – The symbol labeling this transition.

Returns:

A tuple (e, success) where e is an EdgeDescriptor compliant with this Nfa class and success == True if successful, (None, False) otherwise.

alphabet() → set[source]#

Computes the (minimal) alphabet related to this Nfa instance.

Returns:: The corresponding set of symbols.

delta(q: int, a: str) → set[source]#

Transition function, allowing to move from a state q to its a-successor, if any. See also Nfa.delta_word().

Parameters:

q (int) – The vertex descriptor of a state of this Nfa instance.
a (str) – The symbol.

Returns:

The reached states

delta_epsilon(qs: set) → set[source]#

Determines the states reached without consuming any symbol from a subset of states.

Parameters:: qs (iter) – The subset of states.
Returns:: The set of reached states.

delta_one_step(qs: iter, a: str) → set[source]#

Determines the target states reached by consuming a symbol from a subset of states. This function is an implementation detail of the Nfa.delta() method.

Parameters:

qs (iter) – The subset of states.
a (str) – The consumed symbol.

Returns:

The set of reached states.

delta_word(w) → set[source]#

Transition function, allowing to move from an initial state to the state reached by consuming each character of a word w, if any. See also the Nfa.delta() method.

Parameters:: w (str) – The word.
Returns:: The reached states

edges()[source]#

Retrieves an iterator over the transitions involved in this Nfa instance.

Returns:: An iterator over the transitions.

finals() → iter[source]#

Retrieves the final states of this Nfa instance.

Returns:: The final initial states of the NFA.

initials() → set[source]#

Retrieves the initial states of this Nfa instance.

Returns:: The initial states of the NFA.

is_epsilon_transition(e: EdgeDescriptor) → bool[source]#

Tests whether a transition is labeled by the empty word.

Parameters:

e (EdgeDescriptor) – The edge descriptor of the transition.
nfa (Nfa) – A non-deterministic automaton.

Returns:

True if the transition is labeled by the empty word, False otherwise.

is_final(q: int) → bool[source]#

Tests whether state is a final state of this Nfa instance.

Parameters:: q (int) – The vertex descriptor of the considered state.
Returns:: True if q is the final state, None otherwise.

is_initial(q: int) → bool[source]#

Tests whether state is an initial state of this Nfa instance.

Parameters:: q (int) – The vertex descriptor of the considered state.
Returns:: True if q is the initial state, None otherwise.

label(e: EdgeDescriptor) → str[source]#

Retrieves the symbol assigned to a transition of this Nfa instance.

Parameters:: e (EdgeDescriptor) – The edge descriptor of the considered transition.
Returns:: The symbol assigned to the considered transition.

out_edges(q: int)[source]#

Retrieves an iterator over the out-edges of a state q involved in this Nfa instance.

Parameters:: u (int) – The source state.
Returns:: An iterator over the out-edges of u.

remove_edge(e: EdgeDescriptor)[source]#

Removes a transition from this Nfa instance.

Parameters:: e (EdgeDescriptor) – The edge descriptor of the transition to be removed.

set_final(q: int, is_final: bool = True)[source]#

Sets the status of a state as a final state of this Nfa instance.

Parameters:

q (int) – The vertex descriptor of the new initial state.
is_initial (bool) – Pass True if q must be the new initial state, False otherwise.

set_initial(q: int, is_initial: bool = True)[source]#

Sets the status of a state as an initial state of this Nfa instance.

Parameters:

q (int) – The vertex descriptor of the new initial state.
is_initial (bool) – Pass True if q must be the new initial state, False otherwise.

set_initials(q0s: set)[source]#

Sets the initial states of this Nfa instance.

Parameters:: q0s (iter) – The new set of initial states.

sigma(q: int) → set[source]#

Computes sub-alphabet related to a given state of this Nfa instance.

Parameters:: q (int) – The vertex descriptor of the considered state.
Returns:: The corresponding set of symbols.

to_dot(**kwargs) → str[source]#

Exports this Nfa instance to a Graphviz string. See the to_dot() function.

Returns:: The corresponding graphviz string.

delta_word(w: str, nfa: Nfa) → set[source]#

Adapts Automaton.delta_word() for NFAs.

Parameters:

w (str) – The word to consume.
nfa (Nfa) – A non-deterministic automaton.

Returns:

The set of reached states.

epsilon(nfa: Nfa) → str[source]#

Retrieves the symbol representing the empty word.

Parameters:: nfa (Nfa) – A non-deterministic automaton.
Returns:: The symbol representing the empty word.

initials(nfa: Nfa) → iter[source]#

Retrieves the initial states of a NFA.

Parameters:: nfa (Nfa) – A non-deterministic automaton.
Returns:: The initial states of the NFA.

is_epsilon_transition(e: EdgeDescriptor, nfa: Nfa) → bool[source]#

Tests whether a transition is labeled by the empty word.

Parameters:

e (EdgeDescriptor) – The edge descriptor of the transition.
nfa (Nfa) – A non-deterministic automaton.

Returns:

True if the transition is labeled by the empty word, False otherwise.

set_initials(q0s: iter, nfa: Nfa)[source]#

Sets the initial states of a NFA.

Parameters:

q0s (iter) – The new set of initial states.
nfa (Nfa) – A non-deterministic automaton.

pybgl.node_automaton module#

class NodeAutomaton(num_vertices: int = 0, q0: int = 0, pmap_vfinal: ReadWritePropertyMap = None, pmap_vsymbol: ReadWritePropertyMap = None)[source]#

Bases: Automaton

The NodeAutomaton implements a Deterministic Finite Automaton. whose symbols are installed on the states instead of the transitions. This is a particular case of DFA, whose transitions targetting a same given target are all labeled by the same symbol.

Constructor.

Parameters:

num_vertices (int) – The number of states.
q0 (int) – The vertex descriptor of the initial state.
pmap_vfinal (ReadPropertyMap) – A property map which maps each state with a boolean indicating whether its a final state or not.
pmap_vsymbol (ReadPropertyMap) – A property map which maps each state with its corresponding symbol.

add_edge(q: int, r: int) → tuple[source]#

Adds a transition to this NodeAutomaton instance.

Parameters:

q (int) – The vertex descriptor of source state of the new transition.
r (int) – The vertex descriptor of target state of the new transition.
a (str) – The label of the new transition.

Returns:

A tuple (e, success) where e is an EdgeDescriptor compliant with this Automaton class and success == True if successful, (None, False) otherwise.

add_vertex(a: str = None) → int[source]#

Adds a vertex to this Graph instance.

Returns:: The vertex descriptor of the added vertex.

alphabet() → set[source]#

Computes the (minimal) alphabet related to this NodeAutomaton instance.

Returns:: The corresponding set of symbols.

delta(q: int, a: str) → int[source]#

Transition function, allowing to move from a state q to its a-successor, if any.

Parameters:

q (int) – The vertex descriptor of a state of this NodeAutomaton instance.
a (str) – The symbol.

Returns:

The reached state (if any), BOTTOM otherwise.

edge(q: int, r: int) → tuple[source]#

Retrieves the edge from a state q to state r such that r is a a-successor of q in this Automaton instance, if any.

Parameters:

q (int) – The source of the edge.
r (int) – The target of the edge.

Returns:

(e, True) if it exists a single edge from q to r, (None, False) otherwise.

edges() → iter[source]#

Retrieves an iterator over the transitions involved in this NodeAutomaton instance.

Returns:: An iterator over the transitions.

label(e: EdgeDescriptor) → str[source]#

Overloads Automaton.label() to retrieve the label assigned to a transition. The label is just the symbol of the target of the transition.

Parameters:: e (EdgeDescriptor) – The edge descriptor of the considered transition.
Returns:: The symbol assigned to the considered transition.

out_edges(q: int) → iter[source]#

Retrieves an iterator over the out-transitions of a state q involved in this Automaton instance.

Parameters:: q (int) – The source state.
Returns:: An iterator over the out-edges of u.

remove_edge(e: EdgeDescriptor)[source]#

Removes a transition from this NodeAutomaton instance.

Parameters:: e (EdgeDescriptor) – The edge descriptor of the transition to be removed.

sigma(q: int) → set[source]#

Computes sub-alphabet related to a given state of this NodeAutomaton instance.

Parameters:: q (int) – The vertex descriptor of the considered state.
Returns:: The corresponding set of symbols.

symbol(q: int) → str[source]#

Retrieves the symbol installed on a state.

Parameters:: q (int) – The vertex descriptor of the state.
Raises:: KeyError –
Returns:: The corresponding symbol.

to_dot(**kwargs) → str[source]#

Exports this Automaton instance to a Graphviz string. See the to_dot() function.

Returns:: The corresponding Graphviz string.

add_edge(u: int, v: int, g: NodeAutomaton) → tuple[source]#

add_vertex(a: str, g: NodeAutomaton) → int[source]#

edge(u: int, v: int, g: NodeAutomaton) → tuple[source]#

make_node_automaton(transitions: list, pmap_vlabel: ~pybgl.property_map.ReadPropertyMap = None, q0n: int = 0, pmap_vfinal: ~pybgl.property_map.ReadPropertyMap = None, Constructor=<class 'pybgl.node_automaton.NodeAutomaton'>) → NodeAutomaton[source]#

Makes an automaton of type NodeAutomatonClass according to a list of transitions. You may use any arbitrary identifier to characterize the states involved in the transitions.

Parameters:

transitions (list) – The list of transitions, where is each transition is modeled by a (qn, rn, a) tuple and where qn identifies the source of the transition rn identifies the target of the transition and a labels the transition.
pmap_vlabel (ReadPropertyMap) – A property map which maps each state identifier with its corresponding symbol.
q0n (int) – The identifier in transitions of the initial state.
pmap_vfinal (ReadPropertyMap) – A property map which maps each state identifier with a boolean indicating whether the state is final (True) or not (False).
Constructor – The class use to allocate the automaton. Defaults to NodeAutomaton.

Example

>>> from collections import defaultdict
>>> from pybgl import (
...    Automaton, make_assoc_property_map, make_node_automaton
... )
>>> transitions = [("root", "sink"), ("root", "sink")]
>>> map_vlabel = defaultdict(bool, {"root": "a", "sink": "b"})
>>> map_vfinal = defaultdict(bool, {"root": False, "sink": True})
>>> g = make_node_automaton(
...     transitions,
...     q0n="root",
...     pmap_vlabel=make_assoc_property_map(map_vlabel),
...     pmap_vfinal=make_assoc_property_map(map_vfinal)
... )

Returns:: The corresponding NodeAutomatonClass instance.

symbol(q: int, g: NodeAutomaton) → str[source]#

pybgl.parallel_breadth_first_search module#

class ParallelBreadthFirstSearchVisitor[source]#

Bases: object

The ParallelBreadthFirstSearchVisitor class is the base class for any visitor that can be passed to the parallel_breadth_first_search() function.

black_target(e1: EdgeDescriptor, g1: Automaton, e2: EdgeDescriptor, g2: Automaton, a: str)[source]#

Parameters:

e1 (int) – The processed transition of g1 if any, None otherwise .
g1 (Automaton) – The first automaton.
e2 (int) – The processed transition of g2 if any, None otherwise .
g2 (Automaton) – The second automaton.
a (str) – The label of e1 (if not None) and e2 (if not None).

discover_vertex(q1: int, g1: Automaton, q2: int, g2: Automaton)[source]#

Method invoked the first time the algorithm encounters (q1, q2) pair.

Parameters:

q1 (int) – The vertex descriptor of g1 if any, None otherwise .
g1 (Automaton) – The first automaton.
q2 (int) – The vertex descriptor of g2 if any, None otherwise .
g2 (Automaton) – The second automaton.

examine_edge(e1: EdgeDescriptor, g1: Automaton, e2: EdgeDescriptor, g2: Automaton, a: str)[source]#

Method invoked invoked on every out-edge of each pair of states immediately after the vertex is removed from the queue.

Parameters:

e1 (int) – The processed transition of g1 if any, None otherwise .
g1 (Automaton) – The first automaton.
e2 (int) – The processed transition of g2 if any, None otherwise .
g2 (Automaton) – The second automaton.
a (str) – The label of e1 (if not None) and e2 (if not None).

examine_symbol(q1: int, g1: Automaton, q2: int, g2: Automaton, a: str)[source]#

Method invoked when discovering a symbol a when examining the (q1, q2) pair.

Parameters:

q1 (int) – The vertex descriptor of g1 if any, None otherwise .
g1 (Automaton) – The first automaton.
q2 (int) – The vertex descriptor of g2 if any, None otherwise .
g2 (Automaton) – The second automaton.

examine_vertex(q1: int, g1: Automaton, q2: int, g2: Automaton)[source]#

Method invoked for each pair of vertices as it is removed from the queue.

Parameters:

q1 (int) – The vertex descriptor of g1 if any, None otherwise .
g1 (Automaton) – The first automaton.
q2 (int) – The vertex descriptor of g2 if any, None otherwise .
g2 (Automaton) – The second automaton.

finish_vertex(q1: int, g1: Automaton, q2: int, g2: Automaton)[source]#

Method invoked after all of the out-transitions of q1 and q2 have been examined and all of the adjacent vertices have been discovered.

Parameters:

q1 (int) – The vertex descriptor of g1 if any, None otherwise .
g1 (Automaton) – The first automaton.
q2 (int) – The vertex descriptor of g2 if any, None otherwise .
g2 (Automaton) – The second automaton.

gray_target(e1: EdgeDescriptor, g1: Automaton, e2: EdgeDescriptor, g2: Automaton, a: str)[source]#

Method invoked if the target vertex is colored GRAY at the time of examination. The color GRAY indicates that the vertex is currently in the queue.

Parameters:

e1 (int) – The processed transition of g1 if any, None otherwise .
g1 (Automaton) – The first automaton.
e2 (int) – The processed transition of g2 if any, None otherwise .
g2 (Automaton) – The second automaton.
a (str) – The label of e1 (if not None) and e2 (if not None).

start_vertex(s1: int, g1: Automaton, s2: int, g2: Automaton)[source]#

Method invoked when the pair of initial states is pushed to the queue.

Parameters:

q1 (int) – The vertex descriptor of g1 if any, None otherwise .
g1 (Automaton) – The first automaton.
q2 (int) – The vertex descriptor of g2 if any, None otherwise .
g2 (Automaton) – The second automaton.

tree_edge(e1: EdgeDescriptor, g1: Automaton, e2: EdgeDescriptor, g2: Automaton, a: str)[source]#

Method invoked to (in addition to ParallelBreadthFirstSearchVisitor.tree_edge()) if (e1, e2) is a tree edge of the product automaton (g1, g2). The (r1, r2) target vertex of edge the a-transition is discovered at this time.

Parameters:

e1 (int) – The processed transition of g1 if any, None otherwise .
g1 (Automaton) – The first automaton.
e2 (int) – The processed transition of g2 if any, None otherwise .
g2 (Automaton) – The second automaton.
a (str) – The label of e1 (if not None) and e2 (if not None).

parallel_breadth_first_search(g1: Automaton, g2: Automaton, source_pairs: iter = None, pmap_vcolor: ReadWritePropertyMap = None, vis: ParallelBreadthFirstSearchVisitor = None, if_push: callable = None)[source]#

Non-recursive implementation of Depth First Search algorithm, from multiple sources. Based on Boost breadth_first_search, by Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek.

Parameters:

g1 (Automaton) – The first automaton.
g2 (Automaton) – The second automaton.
source_pairs (iter) – An iterable over the pairs of source states. Example: [(g1.initial(), g2.initial())].
pmap_vcolor (ReadWritePropertyMap) – A property map that maps each vertex with its current color (WHITE, GRAY or BLACK)
vis (ParallelBreadthFirstSearchVisitor) – An optional visitor.
if_push (callable) – A callback(e1, g1, e2, g2) -> bool where e1 is an arc of g that returns True if and only if the pair (e1, e2) is relevant.

pybgl.product_mixin module#

class ProductMixin(g12: Automaton, operator)[source]#

Bases: object

The ProductMixin is used to factorize the code in any binary set operation involving two automata.

pybgl.property_map module#

class AssocPropertyMap(d: defaultdict)[source]#

Bases: ReadWritePropertyMap

The AssocPropertyMap is a ReadWritePropertyMap wrapping a defaultdict.

Use the make_assoc_property_map() function to create it.

Constructor.

Parameters:: d (defaultdict) – The underlying dictionary.

class ConstantPropertyMap(value: object)[source]#

Bases: ReadPropertyMap

The ConstantPropertyMap is a ReadPropertyMap which maps any key with a single same value.

Use the make_constant_property_map() function to create it.

Constructor.

Parameters:: value (object) – The only value that is returned by this ConstantPropertyMap instance.

class FuncPropertyMap(f: callable)[source]#

Bases: ReadPropertyMap

The FuncPropertyMap is a ReadPropertyMap which wraps a function.

Use the make_func_property_map() function to create it.

Constructor. You should never call it directly and use the make_func_property_map() instead.

Parameters:: f (callable) – A function which takes a key in parameter and return the corresponding value.

class IdentityPropertyMap[source]#

Bases: ReadPropertyMap

The IdentityPropertyMap is a ReadPropertyMap which maps each key with itself.

Use the identity_property_map() function to create it.

Constructor.

class PropertyMap[source]#

Bases: object

The PropertyMap expose the [] on top of an arbitrary object or function to map. They are used in pybgl to map a vertex or an edge with a given property. Hence, the property map class allows to decide how to organize the metadata related to a graph. One could decide to bundle the vertex properties (resp. properties) in a dedicated class or to use a default dictionary.

An implemented property map must not raise an exception, in particular if they key is not found.

Constructor.

class ReadPropertyMap[source]#

Bases: PropertyMap

The ReadPropertyMap is the base class for any property map with read-only access.

Constructor.

class ReadWritePropertyMap[source]#

Bases: PropertyMap

The ReadWritePropertyMap is the base class for any property map with read and write access.

See also the IdentityPropertyMap and FuncPropertyMap classes.

Constructor.

get(pmap: PropertyMap, k: object) → object[source]#

Retrieves the value related to a key from a property map.

Parameters:

pmap (PropertyMap) – A property map.
k (object) – The key.

Returns:

The corresponding value or the default value of the property map.

identity_property_map()[source]#

Creates a IdentityPropertyMap instance.

Example

>>> pmap = identity_property_map()
>>> pmap[10]
10

make_assoc_property_map(d: defaultdict)[source]#

Makes an AssocPropertyMap instance.

Parameters:: d (defaultdict) – The underlying dictionnary. Do pass a defaultdict instance, not a dict instance.

Example

>>> from collections import defaultdict
>>> d = defaultdict(int)
>>> d['a'] = 7
>>> pmap = make_assoc_property_map(d)
>>> pmap['a'])
7
>>> pmap['a'] = 8
>>> print(pmap['a'])
8
>>> print(pmap['b'])
0

make_constant_property_map(value) → ConstantPropertyMap[source]#

make_func_property_map(f: callable) → FuncPropertyMap[source]#

Makes a FuncPropertyMap instance from a function.

Example

>>> pmap = make_func_property_map(lambda x: x ** 2)
>>> pmap[3]
9

Parameters:: f (callable) – A function which takes a key in parameter and return the corresponding value.
Returns:: The corresponding FuncPropertyMap instance.

put(pmap: ReadWritePropertyMap, k: object, v: object)[source]#

Sets the value related to a key from a property map.

Parameters:

pmap (PropertyMap) – A property map.
k (object) – The key.
v (object) – The new value.

pybgl.prune_incidence_automaton module#

find_reachable_vertices(g: Graph, sources: set) → set[source]#

Returns the set of vertices of a graph which are reachable from a set of source vertices. :param g: Graph, an instance of Graph :param sources: set, a set of integers representing the source vertices

Returns:: The set of vertices that are reachable from the source vertices

prune_incidence_automaton(g: IncidenceAutomaton)[source]#: Prunes the vertices of an IncidenceAutomaton that cannot be reached from the initial state, or that cannot reach a final state. :param g: IncidenceAutomaton, an instance of IncidenceAutomaton

pybgl.regexp module#

compile_dfa(regexp: str, complete: bool = False) → Automaton[source]#

Builds a Deterministic Finite Automaton. from a regular expression.

Parameters:: regexp (str) – A regular expression.
Returns:: A corresponding DFA.

compile_nfa(regexp: str) → Nfa[source]#

Builds a Non-deterministic Finite Automaton from a regular expression.

Parameters:: regexp (str) – A regular expression.
Returns:: A corresponding NFA.

pybgl.reverse module#

reverse_dict(d: dict) → dict[source]#

Reverses a dictionary (swap its key and its values). Note that (key, value) pair may disappear if the values are not unique.

Parameters:: d (dict) – The input dictionary.
Returns:: The reversed dictionary.

reverse_graph(g: IncidenceGraph)[source]#

Flips each arc involved in a graph.

Parameters:: g (IncidenceGraph) – The input graph, updated in place.
Returns:: The flipped graph.

pybgl.revuz_minimize module#

class DefaultRevuzMinimizeVisitor[source]#

Bases: object

merging_states(q1: int, q2: int, g: IncidenceNodeAutomaton)[source]#

Method invoked when two states are about to be merged.

Parameters:

q1 (int) – The first merged state (about to become the merged state).
q2 (int) – The second merged state (about to be removed).
g (IncidenceNodeAutomaton) – The processed automaton.

move_transition(e_old: EdgeDescriptor, e_new: EdgeDescriptor, g: IncidenceNodeAutomaton)[source]#

Method invoked when a transition has just been moved.

Parameters:

e_old (EdgeDescriptor) – The transition before being moved.
e_new (EdgeDescriptor) – The transition after being moved.
g (IncidenceNodeAutomaton) – The processed automaton.

remove_vertex(u: int, g: IncidenceNodeAutomaton)[source]#

Method invoked when a state is about to be removed.

Parameters:

u (int) – The state being removed.
g (IncidenceNodeAutomaton) – The processed automaton.

states_merged(q1: int, q2: int, g: IncidenceNodeAutomaton)[source]#

Method invoked when two states have just been merged as well as their transitions.

Parameters:

q1 (int) – The first merged state (about to become the merged state).
q2 (int) – The second merged state (about to be removed).
g (IncidenceNodeAutomaton) – The processed automaton.

revuz_height(g, pmap_vheight: ReadWritePropertyMap, leaves: set = None) → int[source]#

Computes the height of each vertex starting from its leaves. The leaves have a height equal to 0.

Parameters:

g (IncidenceNodeAutomaton) – The input automaton. It MUST be acyclic.
pmap_vheight (ReadWritePropertyMap) – A ReadWritePropertyMap{VertexDescriptor: int} which maps each vertex with its height.
leaves (set) – The leaves of the g. Pass None to compute this set automatically.

Returns:

The maximum height.

revuz_minimize(g, pmap_vlabel: ReadPropertyMap = None, pmap_elabel: ReadPropertyMap = None, leaves: set = None, vis: DefaultRevuzMinimizeVisitor = None) → int[source]#

Minimizes an acyclic automaton using the Revuz algorithm <https://www.sciencedirect.com/science/article/pii/0304397592901423>.

Parameters:

g (NodeAutomaton or Automaton) – The automaton. It MUST be acyclic.
pmap_vlabel (ReadPropertyMap) – A ReadWritePropertyMap{int: Symbol} that maps each vertex with its symbol. If labeling is purely edge-based, pass None. If g is an Automaton, you may pass None.
pmap_elabel (ReadPropertyMap) – A ReadWritePropertyMap{EdgeDescriptor: Label}. If labeling is purely vertex-based, pass None. If g is a NodeAutomaton, you may pass None.
leaves – The leaves of the IncidenceNodeAutomaton. Pass None to compute this set automatically.

Returns:

The height of g.

pybgl.shunting_yard_postfix module#

class AlgTokenizeVisitor[source]#

Bases: TokenizeVisitor

The AlgTokenizeVisitor specializes the TokenizeVisitor used to implement the tokenizer_alg() function.

Constructor.

on_matched(matched: str, start: int, end: int, s: str)[source]#

Method invoked when a substring has been catched by any pattern of the tokenizer.

Parameters:

unmatched (str) – The matched substring.
start (int) – The starting index of the matched string in the original string.
end (int) – The ending index of the matched string in the original string.
s (str) – The original string.

on_unmatched(unmatched: str, start: int, end: int, s: str)[source]#

Method invoked when a substring has not been catched by any pattern of the tokenizer.

Parameters:

unmatched (str) – The unmatched substring.
start (int) – The starting index of the unmatched string in the original string.
end (int) – The ending index of the unmatched string in the original string.
s (str) – The original string.

class Ast(pmap_vsymbol: ReadWritePropertyMap = None, num_vertices: int = 0, root: int = None)[source]#

Bases: DirectedGraph

The Ast class implements an Abstract Syntax Tree (AST).

Constructor.

Parameters:

pmap_vsymbol (ReadWritePropertyMap) – Maps each vertex with its token. Pass an empty property map.
num_vertices (int) – The number of vertices in the AST. If the AST is empty, pass 0.
root (int) – The vertex descriptor of the root of the AST. If the AST is empty, pass None.

add_vertex(a: str) → int[source]#

Adds a node to this Ast instance.

Parameters:: a (str) – The token assigned to the newly added vertex.
Returns:: The vertex descriptor of the newly added vertex.

children(u: int) → iter[source]#

Retrieves the children of a vertex of this Ast instance.

Parameters:: u (int) – The corresponding vertex descriptor.
Returns:: The corresponding children iterator.

symbol(u: int) → str[source]#

Retrieves the token assigned to a vertex of this Ast instance.

Parameters:: u (int) – The corresponding vertex descriptor.
Returns:: The corresponding token.

to_dot(*cls, **kwargs) → str[source]#

Exports this Graph instance to a Graphviz string. See the to_dot() function.

Returns:: The corresponding graphviz string.

to_expr() → str[source]#

Converts this Ast instance to the corresponding expression.

Returns:: The string containing the expression modeled by this Ast instance.

class CatifyTokenizeVisitor(cat: str = '.')[source]#

Bases: TokenizeVisitor

The AlgTokenizeVisitor specializes the TokenizeVisitor used to implement the catify() function.

Constructor.

Parameters:: cat (str) – The metacharacter used to represent the concatenation operator.

on_matched(matched: str, start: int, end: int, s: str)[source]#

Method invoked when a substring has been catched by any pattern of the tokenizer.

Parameters:

unmatched (str) – The matched substring.
start (int) – The starting index of the matched string in the original string.
end (int) – The ending index of the matched string in the original string.
s (str) – The original string.

on_unmatched(unmatched: str, start: int, end: int, s: str)[source]#

Method invoked when a substring has not been catched by any pattern of the tokenizer.

Parameters:

unmatched (str) – The unmatched substring.
start (int) – The starting index of the unmatched string in the original string.
end (int) – The ending index of the unmatched string in the original string.
s (str) – The original string.

class DefaultShuntingYardVisitor[source]#

Bases: object

The DefaultShuntingYardVisitor is the base class to any visitor passed to the shunting_yard_postfix() function.

on_pop_operator(o: str)[source]#

Method invoked when popping an operator from the input queue.

Parameters:: o (str) – The popped operator.

on_push_operator(o: str)[source]#

Method invoked when pushing an operator to the operator queue.

Parameters:: o (str) – The popped operator.

on_push_output(a: str)[source]#

Method invoked when pushing a token to the output queue.

Parameters:: o (str) – The popped operator.

class Op(cardinality, precedence, associativity)#

Bases: tuple

Create new instance of Op(cardinality, precedence, associativity)

associativity#: Alias for field number 2

cardinality#: Alias for field number 0

precedence#: Alias for field number 1

class RpnDequeAlg(**kwargs)[source]#

Bases: RpnDequeOperation

The RpnDequeAlg implements a queue that can be passed to shunting_yard_postfix() to compute an operation result in a streaming fashion.

See possible applications:

shunting_yard_compute()
shunting_yard_ast()

Constructor.

on_operation(a, op: Op, u: None, vs: list) → float[source]#

Computes an operation.

Parameters:

a (str) – The token corresponding to the processed operator.
op (Op) – The operator specification.
u – Ignored.
vs (list) – The operands.

Returns:

The float containing the operation result.

class RpnDequeAst(*cls, ast: Ast = None, **kwargs)[source]#

Bases: RpnDequeOperation

The RpnDequeAst class implements a queue that can be passed to shunting_yard_postfix() to build in streaming an AST (up-bottom).

For example, if you push "+", then 3, then 2, you are building the AST where the parent node is + and its operands are 2 and 3 and which models the addition 2 + 3.

See the shunting_yard_ast() function.

Constructor.

Parameters:: ast (Ast) – The output AST.

on_append(a: str) → int[source]#

Builds the vertex related to a token pushed in this RpnDequeAst instance.

Parameters:: a (str) – The processed token.
Returns:: The vertex descriptor that corresponds to this token.

on_operation(a, op: Op, u: int, vs: list) → int[source]#

Builds the edges from an operator to its operand in the self.ast AST.

Parameters:

a (str) – The token represening the processed operator.
op (Op) – The operator specifications.
u (int) – The vertex descriptor (operator) of the parent node of the operator node in the AST (another operator).
vs (list) – The list of of vertex descriptors corresponding to each children of the operator node in the AST (operands).

Returns:

The parent vertex descriptor.

class RpnDequeOperation(map_operators: dict, **kwargs)[source]#

Bases: deque

RpnDequeOperation is the base class that implements a queue triggering on_append and on_operation events for the shunting_yard_postfix() function.

Such a queue is handy to process the process handle tokens arriving in the Reverse Polish Notation (RPN).

Constructor.

Parameters:: map_operators (dict) – Maps each operator with its corresponding characteristics. Examples: MAP_OPERATORS_ALG and MAP_OPERATORS_RE.

append(a: str)[source]#

Triggers the RpnDequeOperation.on_append() and RpnDequeOperation.on_operation() methods, possibly overloaded in the children class.

Parameters:: a (str) – The processed token, which may be an operator or an operand.

on_append(a: str) → object[source]#

Method invoked when processing a token is about to be appended to this RpnDequeOperation instance.

Parameters:: a (str) – The token being processed.
Returns:: The parameter u that will be passed in the next on_operation() call.

on_operation(a: str, op: Op, u: object, vs: iter) → object[source]#

Method invoked when processing a token related to an operator.

Parameters:

a (str) – The token representing the operator being processed.
op (Op) – The specification of the operator.
u (object) – The value returned by the last on_append() call.
vs (list) – The operands.

Returns:

The result of the operation.

catify(s: str, cat: str = '.') → iter[source]#

Adds concatenation operator in an input regular expression. It is needed as in standard regular expression, the concatenation operator is implicit. Still, it is required when running the Shunting Yard algorithm. In other words, this function is a pre-processing step required before parsing a regular expression using the Shunting Yard algorithm.

Parameters:

expression – A str containing a regular expression.
is_binary – Callback(chr) -> bool returning True iff the character is a binary operator.
cat – chr representing the concatenation operator.

Returns:

The iter corresponding to expression by adding cat in the appropriate places.

re_escape(s: chr) → str[source]#

Escapes a string that contains that must not be confused with regular expression operators.

Parameters:: s (str) – The string to be escaped.

Example

>>> re_escape("(a.b)+")
... '\(a\.b\)\+'

Returns:: The escaped string.

shunting_yard_ast(expression: iter, map_operators: dict, vis: DefaultShuntingYardVisitor = None) → tuple[source]#

Computes the AST related to a tokenized expression.

Parameters:

expression (iter) – An iter containing a tokenized expression.
map_operators (dict) – A dict{str: Op} mapping operator representation in the input queue and the corresponding operator specification.
vis (DefaultShuntingYardVisitor) – An optional visitor or None.

Returns:

A pair (ast, root) where ast is the Ast instance representing the expression and root is its root node.

shunting_yard_compute(expression: iter, map_operators: dict = {'*': Op(cardinality=2, precedence=3, associativity=1), '+': Op(cardinality=2, precedence=2, associativity=1), '-': Op(cardinality=2, precedence=2, associativity=1), '/': Op(cardinality=2, precedence=3, associativity=1), '^': Op(cardinality=2, precedence=4, associativity=0), 'u+': Op(cardinality=1, precedence=3, associativity=0), 'u-': Op(cardinality=1, precedence=3, associativity=0)}, tokenize: bool = True, vis: DefaultShuntingYardVisitor = None) → float[source]#

Computes the result of an algebraic operation.

Parameters:

expression (iter) – The input operation. It may be either a string (pass tokenize=True), or the corresponding list of tokens (see tokenizer_alg()).
map_operators (dict) – dict{str: Op} mapping the operator string representation in the tokenized input with the corresponding Op specification.
tokenize (bool) – Pass True if expression must be tokenized, False otherwise.
vis (DefaultShuntingYardVisitor) – An optional visitor instance.

Example

>>> shunting_yard_compute("2 + (3 * 40)")
122.0

Returns:: The output float result.

shunting_yard_postfix(expression: iter, map_operators: dict, output: deque = None, vis: DefaultShuntingYardVisitor = None) → deque[source]#

Shunting-yard algorithm (converts infix notation to Reverse Polish Notation).

See this tutorial. The implementation is based on this snippet.

Parameters:

expression (iter) – Tokenized iter containing the input infix notation. Each iteration must move to the next token. Functions like tokenizer_alg, tokenizer_re can help to transform a str to the appropriate iterable.
map_operators (dict) – dict{str: Op} defining the grammar.
output (deque) – The output deque. You could pass a custom class (which implements the method .append), e.g., to run computation in a streaming fashion. See the RpnDequeAlg and the RpnDequeAst classes.
vis (DefaultShuntingYardVisitor) – An optional visitor handling the events raised by this function.

Returns:

The corresponding Reverse Polish Notation.

tokenizer_alg(expression: str) → iter[source]#

Tokenize an algebraic expression.

Parameters:: expression (str) – The input algebraic expression.
Returns:: A list where each element is either a string corresponding to an algebraic operator or a parenthesis, or either a numerical value corresponding to an operand.

Example

>>> tokenizer_alg("(-1 + 22) * 333 / 444")
['(', 'u-', 1.0, '+', 22.0, ')', '*', 333.0, '/', 444.0]

tokenizer_re(expression: str, cat: str = '.') → iter[source]#

Tokenize a regular expression.

Parameters:: expression (str) – The input reular expression.
Returns:: A list where each element is either a string corresponding to a regular expression operator, a parenthesis, or either a literal.

Example

>>> tokenizer_re("[abc]d|e*f+g")
['[abc]', '.', 'd', '|', 'e', '*', '.', 'f', '+', '.', 'g']

pybgl.singleton module#

class Singleton[source]#

Bases: type

The Singleton allows to define singleton classes, i.e. classes that can be instantiated at most once.

>>> class MyClass(metaclass=Singleton): pass
>>> x = MyClass()
>>> y = MyClass()
>>> x is y
True

Based on this thread.

s_instances = {}#

pybgl.strong_components module#

class TarjanVisitor(pmap_component: ReadWritePropertyMap, pmap_root: ReadWritePropertyMap, pmap_discover_time: ReadWritePropertyMap, stack: deque)[source]#

Bases: DefaultDepthFirstSearchVisitor

Constructor.

Parameters:

pmap_component (ReadWritePropertyMap) – Map vertex with its component id Pass an empty property map.
pmap_root (ReadWritePropertyMap) – Map vertex with its root vertex Pass an empty property map.
pmap_discover_time (ReadWritePropertyMap) – Map vertex with its iteration number Pass an empty property map.
stack (deque) – Stack of visited vertices. Pass an empty stack.

discover_min(u: int, v: int) → int[source]#

Determines which vertex has been discovered first.

Parameters:

u (int) – A vertex descriptor.
v (int) – A vertex descriptor.

Returns:

u if u has been discovered before v, v otherwise.

discover_vertex(u: int, g: DirectedGraph)[source]#

Method invoked when a vertex is encountered for the first time.

Parameters:

u (int) – The vertex being discovered.
g (Graph) – The considered graph.

finish_vertex(u: int, g: DirectedGraph)[source]#

Method invoked on a vertex after all of its out edges have been added to the search tree and all of the adjacent vertices have been discovered (but before their out-edges have been examined).

Parameters:

u (int) – The vertex being finished.
g (Graph) – The considered graph.

strong_components(g: DirectedGraph, pmap_component: ReadWritePropertyMap) → int[source]#

Tarjan algorithm, used to discover in O(|V|+|E|) strongly connected component in an arbitrary directed graph.

Based on the boost implementation by Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek

Key ideas: Consider an arbitrary directed graph:

If each strongly connected component is collapsed in a single vertex, the graph is a lattice. It is thus possible to assign a component ID to each vertex such as this lattice orders the component ID.
If the graph is traversed using a DFS, once a vertex is finished, we can assign to it a component.
The ID assigned to a vertex is the number of strongly connected components discovered so far.
The deeper is a component, the higher will be its identifier. The lattice orders the component IDs according to >=.

Parameters:

g (DirectedGraph) – The input graph.
pmap_component (ReadWritePropertyMap) – The output property map that maps each vertex with its component ID (the vertices having the same component ID fall in the same strongly connected component).

pybgl.suffix_trie module#

factors(s: str, max_len: int = None) → iter[source]#

Makes an iterator that lists the factors (substring) of a string s which length is lower than max_len.

Example

>>> sorted(set(factors("banana", 3)))
['', 'a', 'an', 'ana', 'b', 'ba', 'ban', 'n', 'na', 'nan']

Parameters:

s (str) – The input string.
max_len (int) – The maximal length of the factors. Pass None if not needed.

Returns:

The corresponding iterator.

make_suffix_trie(w: str = '', max_len: int = None, g: Trie = None) → Trie[source]#

Makes a Trie instance that gathers all the factors of a given word.

Parameters:

w (str) – The input word.
max_len (int) – The maximal length of the factors stored in the returned Trie instance. Pass None if not needed.
g (Trie) – A reference output Trie instance. Pass None if not needed.

Returns:

The corresponding trie.

slices(n, max_len: int = None) → iter[source]#

Makes an iterator that lists every possible slices between 0 and n that covers an interval which length is lower than max_len.

Example

>>> list(slices(4, 2))
[(0, 0), (0, 1), (0, 2), (1, 2), (1, 3), (2, 3), (2, 4), (3, 4)]

Parameters:

n (int) – The upper bound.
max_len (int) – The maximal length of the ranges. Pass None if not needed.

Returns:

The corresponding iterator.

pybgl.thompson_compile_nfa module#

alternation(nfa1: Nfa, q01: int, f1: int, nfa2: Nfa, q02: int, f2: int) → tuple[source]#

Builds a NFA that implements the | regular expression operator.

Parameters:

g1 (Nfa) – The first NFA made of single initial state and a single final state.
q01 (int) – The initial state of g1.
f1 (int) – The initial state of g1.
g2 (Nfa) – The second NFA made of single initial state and a single final state.
q02 (int) – The initial state of g2.
f2 (int) – The initial state of g2.

Returns:

nfa is a NFA made of single initial state and a single final state that recognizes the language L(g1) | L(g2); q0 is its initial state; f is its initial state.

Return type:

A (nfa, q0, f) tuple, where

bracket(chars: iter) → tuple[source]#

Builds a NFA that recognizes a set of words made of exactly one symbol of the alphabet.

Parameters:: chars (iter) – The recognized symbols.
Returns:: nfa is a NFA made of single initial state and a single final state; q0 is its initial state; f is its initial state.
Return type:: A (nfa, q0, f) tuple, where

concatenation(nfa1: Nfa, q01: int, f1: int, nfa2: Nfa, q02: int, f2: int) → tuple[source]#

Builds a NFA obtained by concatenating two NFAs.

Parameters:

g1 (Nfa) – The first NFA made of single initial state and a single final state.
q01 (int) – The initial state of g1.
f1 (int) – The initial state of g1.
g2 (Nfa) – The second NFA made of single initial state and a single final state.
q02 (int) – The initial state of g2.
f2 (int) – The initial state of g2.

Returns:

nfa is a NFA made of single initial state and a single final state that recognizes the language {s1 + s2 for s1 in L(g1) for s2 in L(g2)} where L returns the language of an automaton; q0 is its initial state; f is its initial state.

Return type:

A (nfa, q0, f) tuple, where

insert_automaton(g1: Nfa, g2: Nfa, map21: dict = None) → dict[source]#

Inserts an NFA in another NFA. In the end, in the first automaton (modified in place), there are two disconnected automata. The states of the second NFA are reindexed to not collide with those already used in the first NFA.

Parameters:

g1 (Nfa) – The first NFA, modified in place.
g2 (Nfa) – The second NFA, not modified.

Returns:

A dictionary precising how the state of g2 have been reindexed once inserted in g1.

literal(a: str) → Nfa[source]#

Builds a NFA that recognizes a single symbol.

Parameters:: a (str) – The considered symbol.
Returns:: nfa is a NFA made of single initial state and a single final state that recognizes the language {a}; q0 is its initial state; f is its initial state;
Return type:: A (nfa, q0, f) tuple, where

one_or_more(nfa: Nfa, q0: int, f: int) → tuple[source]#

Builds a NFA that implements the + regular expression operator (0 or more repetitions).

Parameters:

nfa (Nfa) – A NFA made of single initial state and a single final state.
q0 (int) – The initial state of nfa.
f1 (int) – The initial state of nfa.

Returns:

nfa is a NFA made of single initial state and a single final state; q0 is its initial state; f is its initial state.

Return type:

A (nfa, q0, f) tuple, where

parse_bracket(s: str, whole_alphabet: iter = None) → set[source]#

Parse a [...]-like regular expression (set of symbols).

This function supports:

reversed set of characters (if the first character inside the bracket is ^), (e.g., [^ab] means neither a or b);
range of characters, (e.g., [A-Za-z] corresponds to any latin letter);
escaped characters (see MAP_ESCAPED_BRACKET` and MAP_ESCAPED_SPECIAL`)

Parameters:

s (str) – The parsed regular expression.
whole_alphabet (iter) – The whole alphabet (required to implement the [^...] operator.

Returns:

The corresponding matched characters.

parse_escaped(s: str, whole_alphabet: iter = None) → set[source]#

Parses a regular-expression escaped sequence.

Parameters:

s (str) – The parsed regular expression.
whole_alphabet (iter) – The whole alphabet (required to implement the [^...] operator.

Returns:

The corresponding characters.

parse_repetition(s: str) → tuple[source]#

Parses the {m} and the "{m, n}" operator involved in a regular, where m and n are two integers such that 0 <= m <= n. Regarding the "{m, n}" operator, m and/or n may be omitted (and respectively defaults to 0 and None).

Parameters:

s (str) – The parsed regular expression.

Raises:

RuntimeError –
ValueError –

Returns:

The corresponding (m, n) tuple.

repetition(nfa: Nfa, q0: int, f: int, m: int) → tuple[source]#

Builds the NFA that implements the {m} regular expression operator (exacly m repetitions).

Parameters:

nfa (Nfa) – A NFA made of single initial state and a single final state.
q0 (int) – The initial state of nfa.
f1 (int) – The initial state of nfa.

Returns:

nfa is a NFA made of single initial state and a single final state that recognizes the language {s1 * m for s1 in L(nfa)} where L returns the language of an automaton; q0 is its initial state; f is its initial state.

Return type:

A (nfa, q0, f) tuple, where

repetition_range(nfa: Nfa, q0: int, f: int, m: int, n: int) → tuple[source]#

Builds a NFA that implements the {m, n} regular expression operator (between m and n repetitions).

Parameters:

nfa (Nfa) – A NFA made of single initial state and a single final state.
q0 (int) – The initial state of nfa.
f1 (int) – The initial state of nfa.

Returns:

nfa is a NFA made of single initial state and a single final state; q0 is its initial state; f is its initial state.

Return type:

A (nfa, q0, f) tuple, where

thompson_compile_nfa(expression: str, whole_alphabet: iter = None) → Nfa[source]#

Compiles a NFA from a regular expression using the Thompson transformation.

Parameters:

expression (str) – A regular expression.
whole_alphabet (iter) – The whole alphabet, only needed to process the [^..] operator occurrences.

Returns:

The correspoding NFA, made of single initial state and a single final state.

zero_or_more(nfa: Nfa, q0: int, f: int) → tuple[source]#

Builds a NFA that implements the * regular expression operator (0 or more repetitions).

Parameters:

nfa (Nfa) – A NFA made of single initial state and a single final state.
q0 (int) – The initial state of nfa.
f1 (int) – The initial state of nfa.

Returns:

nfa is a NFA made of single initial state and a single final state; q0 is its initial state; f is its initial state.

Return type:

A (nfa, q0, f) tuple, where

zero_or_one(nfa: Nfa, q0: int, f: int) → tuple[source]#

Builds a NFA that implements the ? regular expression operator (0 or 1 repetition).

Parameters:

nfa (Nfa) – A NFA made of single initial state and a single final state.
q0 (int) – The initial state of nfa.
f1 (int) – The initial state of nfa.

Returns:

nfa is a NFA made of single initial state and a single final state that recognizes the language L(g1) | set() where L returns the language of an automaton; q0 is its initial state; f is its initial state.

Return type:

A (nfa, q0, f) tuple, where

pybgl.tokenize module#

class TokenizeVisitor[source]#

Bases: object

The TokenizeVisitor is the base class to any visitor that can be passed to tokenize().

on_matched(matched: str, start: int, end: int, s: str)[source]#

Method invoked when a substring has been catched by any pattern of the tokenizer.

Parameters:

unmatched (str) – The matched substring.
start (int) – The starting index of the matched string in the original string.
end (int) – The ending index of the matched string in the original string.
s (str) – The original string.

on_unmatched(unmatched: str, start: int, end: int, s: str)[source]#

Method invoked when a substring has not been catched by any pattern of the tokenizer.

Parameters:

unmatched (str) – The unmatched substring.
start (int) – The starting index of the unmatched string in the original string.
end (int) – The ending index of the unmatched string in the original string.
s (str) – The original string.

tokenize(tokenizer, s: str, vis: TokenizeVisitor = None)[source]#: Regexp-based string tokenizer. Useful to parse string when processing involve multiple regular expressions. See e.g. the escape_html() function.

pybgl.topological_sort module#

class TopologicalSortVisitor(stack)[source]#

Bases: DefaultDepthFirstSearchVisitor

Constructor.

Parameters:: stack (deque) – The stack used to compute the topological sorting.

back_edge(e: EdgeDescriptor, g: DirectedGraph)[source]#

Method invoked on the back edges in the graph.

Parameters:

e (EdgeDescriptor) – The considered back edge.
g (Graph) – The considered graph.

finish_vertex(u: int, g: DirectedGraph)[source]#

Method invoked on a vertex after all of its out edges have been added to the search tree and all of the adjacent vertices have been discovered (but before their out-edges have been examined).

Parameters:

u (int) – The vertex being finished.
g (Graph) – The considered graph.

topological_sort(g: DirectedGraph, stack: deque = None) → deque[source]#

Computes a topological sorting of a graph. The implementation is based on boost/graph/topological_sort.hpp.

Parameters:

g (DirectedGraph) – The input graph. It must be a DAG <https://en.wikipedia.org/wiki/Directed_acyclic_graph>.
stack (deque) – The stack used to store the topological sort, updated in place. You may pass None to use the default stack.

Returns:

The stack containing the vertices, sorted by topological order.

pybgl.trie module#

class Trie(*args, **kwargs)[source]#

Bases: Automaton

A trie is, also called digital tree or prefix tree, is a type of k-ary search tree, a tree data structure used for locating specific keys from within a set.

The Trie specializes the Automaton class for trees.

Constructor.

Parameters:

num_vertices (int) – Pass the (initial) number of vertices.
q0 (int) – The vertex descriptor of the initial state.
pmap_vfinal (ReadPropertyMap) – A ReadPropertyMap that maps a vertex descriptor with a boolean which equals True if the vertex is a final state None otherwise.

insert(x: object)[source]#

Parameters:: x (str or Trie) – A str or a Trie instance, inserted in this Trie instance.

num_edges() → int[source]#

Counts the number of edges involved in this Graph instance.

Returns:: The number of edges.

class TrieDeterministicFusion[source]#

Bases: ParallelBreadthFirstSearchVisitor

The TrieDeterministicFusion is used to implement the trie_deterministic_fusion() function.

Constructor.

examine_edge(e1: EdgeDescriptor, g1: Trie, e2: EdgeDescriptor, g2: Trie, a: str)[source]#

Method invoked invoked on every out-edge of each pair of states immediately after the vertex is removed from the queue.

Parameters:

e1 (int) – The processed transition of g1 if any, None otherwise .
g1 (Automaton) – The first automaton.
e2 (int) – The processed transition of g2 if any, None otherwise .
g2 (Automaton) – The second automaton.
a (str) – The label of e1 (if not None) and e2 (if not None).

start_vertex(q01: int, g1: Trie, q02: int, g2: Trie)[source]#

Method invoked when the pair of initial states is pushed to the queue.

Parameters:

q1 (int) – The vertex descriptor of g1 if any, None otherwise .
g1 (Automaton) – The first automaton.
q2 (int) – The vertex descriptor of g2 if any, None otherwise .
g2 (Automaton) – The second automaton.

trie_deterministic_fusion(g1: Trie, g2: Trie)[source]#

Merges two Trie instance. The first instance is updated in place.

Parameters:

g1 (Trie) – The first Trie instance, modified in place.
g2 (Trie) – The second Trie instance (unmodified).

pybgl.trie_matching module#

class TrieMatchingVisitor[source]#

Bases: ParallelBreadthFirstSearchVisitor

The TrieMatchingVisitor is used to implement the trie_matching() function.

Constructor.

discover_vertex(s1: int, g1: Trie, s2: int, g2: Trie)[source]#

Method invoked the first time the algorithm encounters (q1, q2) pair.

Parameters:

q1 (int) – The vertex descriptor of g1 if any, None otherwise .
g1 (Automaton) – The first automaton.
q2 (int) – The vertex descriptor of g2 if any, None otherwise .
g2 (Automaton) – The second automaton.

start_vertex(s1: int, g1: Trie, s2: int, g2: Trie)[source]#

Method invoked when the pair of initial states is pushed to the queue.

Parameters:

q1 (int) – The vertex descriptor of g1 if any, None otherwise .
g1 (Automaton) – The first automaton.
q2 (int) – The vertex descriptor of g2 if any, None otherwise .
g2 (Automaton) – The second automaton.

update(q1: int, g1: Trie, q2: int, g2: Trie)[source]#: Internal method, used to update self.counters.

trie_matching(g1: Trie, g2: Trie, vis: TrieMatchingVisitor = None) → list[source]#

Checks how two Trie instances overlap. If you want to restrict which parts of g1 and g2 must be explored, see the GraphView class.

Parameters:

g1 (Trie) – The first Trie instance.
g2 (Trie) – The second Trie instance.
vis (TrieMatchingVisitor) – An optional visitor

Module contents#

Top-level package.