Package tulip :: Package transys :: Module labeled_graphs :: Class LabeledDiGraph

Class LabeledDiGraph

Directed multi-graph with constrained labeling.

Provides facilities to define labeling functions on
vertices and edges, with given co-domains,
so that labels are type-checked, not arbitrary.

Each state (or edge) is annotated with labels.
Before removing a value from a label type,
first make sure no state (or edge) is labeled with it.

Multiple edges with the same C{attr_dict} are not possible.
So the difference from C{networkx.MultiDiGraph} is that
the C{dict} of edges between u,v is a bijection.

Between two nodes either:

  - a single unlabeled edge exists (no labeling constraints), or
  - labeled edges exist

but mixing labeled with unlabeled edges for the same
edge is not allowed, to simplify and avoid confusion.


Label types by example
======================

Use a C{dict} for each label type you want to define,
like this:

  >>> types = [
          {'name': 'drink',
           'values': {'tea', 'coffee'},
           'setter': True,
           'default': 'tea'}]

This will create a label type named C{'drink'} that can
take the values C{'tea'} and C{'coffee'}.

Assuming this label type applies to nodes,
you can now label a new node as:

  >>> g = LabeledDiGraph(types)
  >>> g.add_node(1, drink='coffee')

If you omit the label when adding a new node,
it gets the default value:

  >>> g.add_node(2)
  >>> g.node[2]
  {'drink': 'tea'}

The main difference with vanilla C{networkx} is
that the dict above includes type checking:

  >>> type(g.node[2])
  tulip.transys.mathset.TypedDict

The C{'setter'} key with value C{True}
creates also a field C{g.drink}.
Be careful to avoid name conflicts with existing
networkx C{MultiDiGraph} attributes.

This allows us to add more values after creating
the graph:

  >>> g.drink
  {'coffee', 'tea'}
  >>> g.drink.add('water')
  {'coffee', 'tea', 'water'}

Finally, the graph will prevent us from
accidentally using an untyped label name,
by raising an C{AttributeError}:

  >>> g.add_node(3, day='Jan')
  AttributeError: ...

To add untyped labels, do so explicitly:

  >>> g.add_node(3, day='Jan', check=False)
  >>> g.node[3]
  {'day': 'Jan', 'drink': 'tea'}


Details on label types
======================

Each label type is defined by a C{dict} that
must have the keys C{'name'} and C{'values'}:

  - C{'name'}: with C{str} value

  - C{'values' : B} implements C{__contains__}
    used to check label validity.

    If you want the codomain C{B} to be
    extensible even after initialization,
    it must implement method C{add}.

and optionally the keys:

  - C{'setter': C} with 3 possibilities:

    - if absent,
      then no C{setter} attribute is created

    - otherwise an attribute C{self.A}
      is created, pointing at:

        - the given co-domain C{B}
          if C{C is True}

        - C{C}, otherwise.

  - C{'default': d} is a value in C{B}
    to be returned for node and edge labels
    not yet explicitly specified by the user.

@param node_label_types: applies to nodes, as described above.
@type node_label_types: C{list} of C{dict}

@param edge_label_types: applies to edges, as described above.
@type node_label_types: C{list} of C{dict}

@param deterministic: if True, then edge-label-deterministic


Deprecated dot export
=====================

BEWARE: the dot interface will be separated from
the class itself. Some basic style definitions as
below may remain, but masking selected labels and
other features will be accessible only via functions.

For dot export subclasses must define:

    - _state_label_def
    - _state_dot_label_format

    - _transition_label_def
    - _transition_dot_label_format
    - _transition_dot_mask

Note: this interface will be improved in the future.


Credits
=======

Some code in overridden methods of C{networkx.MultiDiGraph}
is adapted from C{networkx}, which is distributed under a BSD license.

Nested Classes

Inherited from networkx.classes.multigraph.MultiGraph: edge_key_dict_factory

Inherited from networkx.classes.graph.Graph: adjlist_dict_factory, edge_attr_dict_factory, node_dict_factory

Instance Methods

__init__(self, node_label_types=None, edge_label_types=None, deterministic=False)
Initialize a graph with edges, name, graph attributes.

bool

is_consistent(self)
Check if labels are consistent with their type definitions.

add_node(self, n, attr_dict=None, check=True, **attr)
Use a TypedDict as attribute dict.

add_nodes_from(self, nodes, check=True, **attr)
Create or label multiple nodes.

add_edge(self, u, v, key=None, attr_dict=None, check=True, **attr)
Use a TypedDict as attribute dict.

add_edges_from(self, labeled_ebunch, attr_dict=None, check=True, **attr)
Add multiple labeled edges.

remove_labeled_edge(self, u, v, attr_dict=None, **attr)
Remove single labeled edge.

remove_labeled_edges_from(self, labeled_ebunch, attr_dict=None, **attr)
Remove labeled edges.

has_deadends(self)
Return False if all nodes have outgoing edges.

remove_deadends(self)
Recursively delete nodes with no outgoing transitions.

dot_str(self, wrap=10, **kwargs)
Return dot string.

bool

save(self, filename=None, fileformat=None, rankdir='LR', prog=None, wrap=10, tikz=False)
Save image to file.

plot(self, rankdir='LR', prog=None, wrap=10, ax=None)
Plot image using dot.

Inherited from networkx.classes.multidigraph.MultiDiGraph: degree_iter, edges_iter, in_degree_iter, in_edges, in_edges_iter, is_directed, is_multigraph, out_degree_iter, out_edges, out_edges_iter, remove_edge, reverse, subgraph, to_directed, to_undirected

Inherited from networkx.classes.multigraph.MultiGraph: edges, get_edge_data, has_edge, number_of_edges, remove_edges_from, selfloop_edges

Inherited from networkx.classes.digraph.DiGraph: clear, has_predecessor, has_successor, in_degree, neighbors, neighbors_iter, out_degree, predecessors, predecessors_iter, remove_node, remove_nodes_from, successors, successors_iter

Inherited from networkx.classes.graph.Graph: __contains__, __getitem__, __iter__, __len__, __str__, add_cycle, add_path, add_star, add_weighted_edges_from, adjacency_iter, adjacency_list, copy, degree, has_node, nbunch_iter, nodes, nodes_iter, nodes_with_selfloops, number_of_nodes, number_of_selfloops, order, size

Inherited from object: __delattr__, __format__, __getattribute__, __hash__, __new__, __reduce__, __reduce_ex__, __repr__, __setattr__, __sizeof__, __subclasshook__

Properties

Inherited from networkx.classes.graph.Graph: name

Inherited from object: __class__

Method Details

init(self, node_label_types=None, edge_label_types=None, deterministic=False)
(Constructor)

Initialize a graph with edges, name, graph attributes.

Parameters
----------
data : input graph
    Data to initialize graph.  If data=None (default) an empty
    graph is created.  The data can be an edge list, or any
    NetworkX graph object.  If the corresponding optional Python
    packages are installed the data can also be a NumPy matrix
    or 2d ndarray, a SciPy sparse matrix, or a PyGraphviz graph.
name : string, optional (default='')
    An optional name for the graph.
attr : keyword arguments, optional (default= no attributes)
    Attributes to add to graph as key=value pairs.

See Also
--------
convert

Examples
--------
>>> G = nx.Graph()   # or DiGraph, MultiGraph, MultiDiGraph, etc
>>> G = nx.Graph(name='my graph')
>>> e = [(1,2),(2,3),(3,4)] # list of edges
>>> G = nx.Graph(e)

Arbitrary graph attribute pairs (key=value) may be assigned

>>> G=nx.Graph(e, day="Friday")
>>> G.graph
{'day': 'Friday'}

Overrides: object.__init__: (inherited documentation)

is_consistent(self)

Check if labels are consistent with their type definitions.

Use case: removing values from a label type can invalidate existing labels that use them.

Returns: bool

add_node(self, n, attr_dict=None, check=True, **attr)

Use a TypedDict as attribute dict.

Overrides networkx.MultiDiGraph.add_node, see that for details.

Log warning if node already exists. All other functionality remains the same.

Parameters:

check - if True and untyped keys are passed, then raise AttributeError.

Overrides: networkx.classes.graph.Graph.add_node

add_nodes_from(self, nodes, check=True, **attr)

Create or label multiple nodes.

Overrides networkx.MultiDiGraph.add_nodes_from, for details see that and LabeledDiGraph.add_node.

Overrides: networkx.classes.graph.Graph.add_nodes_from

add_edge(self, u, v, key=None, attr_dict=None, check=True, **attr)

Use a TypedDict as attribute dict.

Overrides networkx.MultiDiGraph.add_edge, see that for details.

Raise ValueError if u or v are not already nodes.
Raise Exception if edge (u, v, {}) exists.
Log warning if edge (u, v, attr_dict) exists.
Raise ValueError if attr_dict contains typed key with invalid value.
Raise AttributeError if attr_dict contains untyped keys, unless check=False.

Each label defines a different labeled edge. So to "change" the label, either:

remove the edge with this label, then add a new one, or
find the edge key, then use subscript notation:
G[i][j][key]['attr_name'] = attr_value

Notes

Argument key has been removed compared to networkx.MultiDiGraph.add_edge, because edges are defined by their labeling, i.e., multiple edges with same labeling are not allowed.

Parameters:

check - raise AttributeError if attr_dict has untyped attribute keys, otherwise warn

Overrides: networkx.classes.graph.Graph.add_edge

add_edges_from(self, labeled_ebunch, attr_dict=None, check=True, **attr)

Add multiple labeled edges.

Overrides networkx.MultiDiGraph.add_edges_from, see that for details.

Only difference is that only 2 and 3-tuple edges allowed. Keys cannot be specified, because a bijection is maintained.

Parameters:

labeled_ebunch - iterable container of:
- 2-tuples: (u, v), or
- 3-tuples: (u, v, label)
See also remove_labeled_edges_from.

Overrides: networkx.classes.graph.Graph.add_edges_from

remove_labeled_edge(self, u, v, attr_dict=None, **attr)

Remove single labeled edge.

Parameters:

attr_dict (dict) - attributes with which to identify the edge.
attr - keyword arguments with which to update attr_dict.

remove_labeled_edges_from(self, labeled_ebunch, attr_dict=None, **attr)

Remove labeled edges.

Example

>>> g = LabeledDiGraph()
>>> g.add_edge(1, 2, day='Mon')
>>> g.add_edge(1, 2, day='Tue')
>>> edges = [(1, 2, {'day':'Mon'}),
             (1, 2, {'day':'Tue'})]
>>> g.remove_edges_from(edges)

Parameters:

labeled_ebunch - iterable container of edge tuples Each edge tuple can be:
- 2-tuple: (u, v) All edges between u and v are removed.
- 3-tuple: (u, v, attr_dict) all edges between u and v annotated with that attr_dict are removed.

has_deadends(self)

Return False if all nodes have outgoing edges.

Edge labels are not taken into account.

dot_str(self, wrap=10, **kwargs)

Return dot string.

Requires pydot.

save(self, filename=None, fileformat=None, rankdir=`'LR'`, prog=None, wrap=10, tikz=False)

Save image to file.

Recommended file formats:

tikz (via dot2tex)
pdf
svg
dot
png

Any other format supported by pydot.write is available.

Experimental:

html (uses d3.js)
'scxml'

Requires

graphviz dot: http://www.graphviz.org/
pydot: https://pypi.python.org/pypi/pydot

and for tikz:

dot2tex: https://pypi.python.org/pypi/dot2tex
dot2texi: http://www.ctan.org/pkg/dot2texi (to automate inclusion)

Depends

dot and either of IPython or Matplotlib

Class LabeledDiGraph

__init__(self, node_label_types=None, edge_label_types=None, deterministic=False) (Constructor)

is_consistent(self)

add_node(self, n, attr_dict=None, check=True, **attr)

add_nodes_from(self, nodes, check=True, **attr)

add_edge(self, u, v, key=None, attr_dict=None, check=True, **attr)

Notes

add_edges_from(self, labeled_ebunch, attr_dict=None, check=True, **attr)

remove_labeled_edge(self, u, v, attr_dict=None, **attr)

remove_labeled_edges_from(self, labeled_ebunch, attr_dict=None, **attr)

Example

has_deadends(self)

dot_str(self, wrap=10, **kwargs)

save(self, filename=None, fileformat=None, rankdir='LR', prog=None, wrap=10, tikz=False)

Requires

See Also

plot(self, rankdir='LR', prog=None, wrap=10, ax=None)

See Also

Depends

init(self, node_label_types=None, edge_label_types=None, deterministic=False)
(Constructor)

save(self, filename=None, fileformat=None, rankdir=`'LR'`, prog=None, wrap=10, tikz=False)

plot(self, rankdir=`'LR'`, prog=None, wrap=10, ax=None)