Ask Your Question
1

How to get an arbitrary orientation of a graph.

asked 2016-09-04 07:59:18 +0100

GA316 gravatar image

updated 2017-07-31 22:06:09 +0100

FrédéricC gravatar image

I want to know how to get the iterator of all orientations of a given graph G.

Thanks for your valuable timing.

There is another question in the same title, unfortunately that question has irrelevant title. https://ask.sagemath.org/question/983...

edit retag flag offensive close merge delete

1 Answer

Sort by » oldest newest most voted
1

answered 2016-09-04 11:01:28 +0100

tmonteil gravatar image

updated 2016-09-05 22:41:21 +0100

The lasiest way is hacking an existing method: you can just mimic the code of the to_directed and add a loop iterating over subsets of (possibly labeled, possibly multiple,...) edges as follows (note that you can see the code of to_directed by typing G.to_directed?? for some graph G).

The only differences will be:

  • give the orientation name to the function

  • a loop over the orientations:

    for orient in subsets(self.edges()):
    
  • an if then else test to know whether we have to add one edge or the other

  • return D is replaced with yield D to make an iterator (instead of returning the first orientation found).

So, the code you might get is:

def orientations(self, implementation='c_graph', data_structure=None,
                sparse=None):
    """
    Iterates over all orientations of self.

    INPUT:

     - ``data_structure`` -- one of ``"sparse"``, ``"static_sparse"``, or
       ``"dense"``. See the documentation of :class:`Graph` or
       :class:`DiGraph`.

     - ``sparse`` (boolean) -- ``sparse=True`` is an alias for
       ``data_structure="sparse"``, and ``sparse=False`` is an alias for
       ``data_structure="dense"``.
    """
    if sparse is not None:
        if data_structure is not None:
            raise ValueError("The 'sparse' argument is an alias for "
                             "'data_structure'. Please do not define both.")
        data_structure = "sparse" if sparse else "dense"
    if data_structure is None:
        from sage.graphs.base.dense_graph import DenseGraphBackend
        from sage.graphs.base.sparse_graph import SparseGraphBackend
        if isinstance(self._backend, DenseGraphBackend):
            data_structure = "dense"
        elif isinstance(self._backend, SparseGraphBackend):
            data_structure = "sparse"
        else:
            data_structure = "static_sparse"
    from sage.graphs.all import DiGraph
    for orient in subsets(self.edges()):
        D = DiGraph(name           = self.name(),
                    pos            = self._pos,
                    multiedges     = self.allows_multiple_edges(),
                    loops          = self.allows_loops(),
                    implementation = implementation,
                    data_structure = (data_structure if data_structure!="static_sparse"
                                      else "sparse")) # we need a mutable copy
        D.add_vertices(self.vertex_iterator())
        for u,v,l in self.edge_iterator():
            if (u,v,l) in orient:
                D.add_edge(u,v,l)
            else:
                D.add_edge(v,u,l)
        if hasattr(self, '_embedding'):
            D._embedding = copy(self._embedding)
        D._weighted = self._weighted
        if data_structure == "static_sparse":
            D = D.copy(data_structure=data_structure)
        yield D

You can test it on a small example to see if it satisfies your need:

sage: G = graphs.CycleGraph(3)
sage: G.plot()
sage: for i in orientations(G):
....:     i.plot()

It should also work for multiedges graphs, you can decide which implementation/data structure you want for the oriented graphs, the sparsity, to keep the embedding, etc.

EDIT see also trac ticket 21415.

edit flag offensive delete link more

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower

Stats

Asked: 2016-09-04 07:59:18 +0100

Seen: 536 times

Last updated: Sep 05 '16