summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorMichele Borassi <michele.borassi@imtlucca.it>2015-07-20 17:03:33 +0200
committerMichele Borassi <michele.borassi@imtlucca.it>2015-07-28 12:42:54 +0200
commit222c2dc462744658845b5a84d6c1c2ce33b3881d (patch)
tree1a049f227a04696c765575522d0b9d7287ed4cf9
parentIncluded igraph in sage. (diff)
Conversion Sage graphs - igraph graphs
-rw-r--r--src/sage/graphs/digraph.py28
-rw-r--r--src/sage/graphs/generic_graph.py30
-rw-r--r--src/sage/graphs/graph.py19
3 files changed, 75 insertions, 2 deletions
diff --git a/src/sage/graphs/digraph.py b/src/sage/graphs/digraph.py
index 029b963..a2b0998 100644
--- a/src/sage/graphs/digraph.py
+++ b/src/sage/graphs/digraph.py
@@ -206,6 +206,8 @@ class DiGraph(GenericGraph):
#. A NetworkX digraph
+ #. An igraph Graph (see http://igraph.org/python/)
+
- ``pos`` - a positioning dictionary: for example, the
spring layout from NetworkX for the 5-cycle is::
@@ -243,6 +245,8 @@ class DiGraph(GenericGraph):
- ``NX`` - data must be a NetworkX DiGraph.
+ - ``igraph`` - data must be an igraph Graph.
+
.. NOTE::
As Sage's default edge labels is ``None`` while NetworkX uses
@@ -398,6 +402,13 @@ class DiGraph(GenericGraph):
sage: DiGraph(g)
Digraph on 5 vertices
+ #. An igraph Graph::
+
+ sage: import igraph
+ sage: g = igraph.Graph([(0,1),(1,2),(0,2)], directed = True)
+ sage: DiGraph(g)
+ Digraph on 3 vertices
+
TESTS::
sage: DiGraph({0:[1,2,3], 2:[4]}).edges()
@@ -443,6 +454,14 @@ class DiGraph(GenericGraph):
sage: type(J_imm._backend) == type(G_imm._backend)
True
+ If the input is an undirected igraph graph, the output is transformed into
+ a directed graph::
+
+ sage: import igraph
+ sage: G = igraph.Graph([(0,1),(1,2),(0,2)], directed = False)
+ sage: H = DiGraph(G)
+ sage: H.edges(labels=False)
+ [(0, 1), (0, 2), (1, 0), (1, 2), (2, 0), (2, 1)]
"""
_directed = True
@@ -613,6 +632,9 @@ class DiGraph(GenericGraph):
format = 'NX'
elif isinstance(data, (networkx.DiGraph, networkx.MultiDiGraph)):
format = 'NX'
+ import igraph
+ if format is None and isinstance(data, igraph.Graph):
+ format = 'igraph'
if format is None and isinstance(data, (int, Integer)):
format = 'int'
if format is None and data is None:
@@ -850,6 +872,12 @@ class DiGraph(GenericGraph):
self.allow_loops(loops,check=False)
self.add_vertices(data.nodes())
self.add_edges((u,v,r(l)) for u,v,l in data.edges_iter(data=True))
+ elif format == 'igraph':
+ if data.is_directed():
+ self.add_edges(data.get_edgelist())
+ else:
+ self.add_edges(data.get_edgelist())
+ self.add_edges([(w,v) for (v,w) in data.get_edgelist()])
elif format == 'int':
if weighted is None: weighted = False
self.allow_loops(True if loops else False,check=False)
diff --git a/src/sage/graphs/generic_graph.py b/src/sage/graphs/generic_graph.py
index 55550b5..cc393fe 100644
--- a/src/sage/graphs/generic_graph.py
+++ b/src/sage/graphs/generic_graph.py
@@ -12,6 +12,7 @@ can be applied on both. Here is what it can do:
:delim: |
:meth:`~GenericGraph.networkx_graph` | Create a new NetworkX graph from the Sage graph
+ :meth:`~GenericGraph.igraph_graph` | Create a new igraph graph from the Sage graph
:meth:`~GenericGraph.to_dictionary` | Create a dictionary encoding the graph.
:meth:`~GenericGraph.copy` | Return a copy of the graph.
:meth:`~GenericGraph.export_to_file` | Export the graph to a file.
@@ -1310,6 +1311,35 @@ class GenericGraph(GenericGraph_pyx):
N.add_edge(u,v,weight=l)
return N
+ def igraph_graph(self):
+ r"""
+ Converts the graph into an igraph graph.
+
+ For more information on the Python version of igraph, see
+ http://igraph.org/python/.
+
+ EXAMPLES::
+
+ sage: G = graphs.TetrahedralGraph()
+ sage: H = G.igraph_graph()
+ sage: H.summary()
+ 'IGRAPH U--- 4 6 -- '
+ sage: G = digraphs.Path(3)
+ sage: H = G.igraph_graph()
+ sage: H.summary()
+ 'IGRAPH D--- 3 2 -- '
+ """
+
+ import igraph
+ v_to_int = {v:i for i,v in enumerate(self.vertices())}
+ edgelist = [(v_to_int[v],v_to_int[w])
+ for v,w in self.edges(labels=False)]
+ if self.is_directed():
+ g = igraph.Graph(edgelist, directed=True)
+ else:
+ g = igraph.Graph(edgelist, directed=False)
+ return g
+
def to_dictionary(self, edge_labels=False, multiple_edges=False):
r"""
Returns the graph as a dictionary.
diff --git a/src/sage/graphs/graph.py b/src/sage/graphs/graph.py
index 0850bed..20e68f6 100644
--- a/src/sage/graphs/graph.py
+++ b/src/sage/graphs/graph.py
@@ -626,6 +626,8 @@ class Graph(GenericGraph):
#. A NetworkX graph
+ #. An igraph graph (see http://igraph.org/python/)
+
- ``pos`` - a positioning dictionary: for example, the
spring layout from NetworkX for the 5-cycle is::
@@ -679,6 +681,8 @@ class Graph(GenericGraph):
- ``NX`` - data must be a NetworkX Graph.
+ - ``igraph`` - data must be an igraph Graph.
+
.. NOTE::
As Sage's default edge labels is ``None`` while NetworkX uses
@@ -953,6 +957,13 @@ class Graph(GenericGraph):
sage: DiGraph(g)
Digraph on 5 vertices
+ #. An igraph graph::
+
+ sage: import igraph
+ sage: g = igraph.Graph([(0,1),(0,2)])
+ sage: Graph(g)
+ Graph on 3 vertices
+
By default, graphs are mutable and can thus not be used as a dictionary
key::
@@ -1164,9 +1175,11 @@ class Graph(GenericGraph):
import networkx
if isinstance(data, (networkx.DiGraph, networkx.MultiDiGraph)):
data = data.to_undirected()
- format = 'NX'
elif isinstance(data, (networkx.Graph, networkx.MultiGraph)):
format = 'NX'
+ import igraph
+ if format is None and isinstance(data, igraph.Graph):
+ format = 'igraph'
if format is None and isinstance(data, (int, Integer)):
format = 'int'
if format is None and data is None:
@@ -1377,6 +1390,8 @@ class Graph(GenericGraph):
self.allow_multiple_edges(multiedges, check=False)
self.add_vertices(data.nodes())
self.add_edges((u,v,r(l)) for u,v,l in data.edges_iter(data=True))
+ elif format == 'igraph':
+ self.add_edges(data.get_edgelist())
elif format == 'rule':
f = data[1]
verts = data[0]
@@ -6071,7 +6086,7 @@ class Graph(GenericGraph):
for x in IndependentSets(self, complement = True):
number_of[len(x)] += 1
return sum(coeff*t**i for i,coeff in enumerate(number_of) if coeff)
-
+
### Miscellaneous
def cores(self, k = None, with_labels=False):