Message Boards Message Boards

Little pieces of code for graph and networks theory

I thought it would be nice to have a discussion of little pieces of Mathematica code that can help when working with graphs and networks. Here for example, one to undirect graphs when needed:
ToUndirectedGraph[dirGraph_] :=
Graph[VertexList@dirGraph, #[[1]] \[UndirectedEdge] #[[2]] & /@
   Union[Sort[{#[[1]], #[[2]]}] & /@ EdgeList@dirGraph]]
or what about a graph planarity check function (i.e. adding any edge would destroy its planarity):
 MaxPlanarQ[graph_] :=
  PlanarGraphQ[graph] &&
   With[{pos =
      Select[Position[Normal@AdjacencyMatrix@graph,
        0], #[[1]] < #[[2]] &],
     vertex = VertexList[graph],
     edges = EdgeList[graph]
     },
    val = True; 
   Do[If[PlanarGraphQ[
      Graph[Append[edges,
        vertex[[i[[1]]]] \[UndirectedEdge] vertex[[i[[2]]]]]]],
     val = False; Break[]], {i, pos}]; Return[val]]
And one to produce random permutations for a given graph with the indicated number n of nodes:
PermuteGraph[g_, n_] :=
Table[AdjacencyMatrix@
   Graph[RandomSample[VertexList@g], EdgeList@g], {n}]
What about code for counting sizes of graph automorphism groups? I have some, but it uses Saucy, an open-source software that has been tested to be (surprisingly) in practice very fast, despite the NP question underlying this task (unknown whether it has a polynomial time algorithm or it is NP-complete). There is a function in Combnatorica but you can read about its drawbacks in the graph automorphism page in MathWorld.
POSTED BY: Hector Zenil
9 Replies

That is useful to know about IGReorderVertices, thanks.

POSTED BY: Hector Zenil

Actually, I wouldn't call what IGReorderVertices does relabelling. It really just changes the order in which vertices are stored. This in turn affects how certain functions work: the result of AdjacencyMatrix, the order in which BetweennessCentrality returns results, or what DirectedGraph[graph, "Acyclic"] does. It's more about changing the practical representation of the graph than doing anything of mathematical significance.

For true relabelling, you can use VertexReplace.

Example:

If we have

g = Graph[{1, 2, 3}, {1 <-> 2, 2 <-> 3}]

then

IGReorderVertices[{1, 3, 2}, g] returns the equivalent of

g = Graph[{1, 3, 2}, {1 <-> 2, 2 <-> 3}]

Note that the edge list has not changed. 2 is still the "middle" vertex.

VertexReplace[g, {1 -> 1, 2 -> 3, 3 -> 2}] return the equivalent of

g = Graph[{1, 3, 2}, {1 <-> 3, 3 <-> 2}]

Now the edge list has changed too, as 2 was renamed to 3 and 3 was renamed to 2.

If the relabelling is an isomorphic one, then of course the edge list doesn't change (by definition), except in its ordering. Thus, in this case, either function could be used.

In[19]:= perms = GroupElements@GraphAutomorphismGroup[g]
Out[19]= {Cycles[{}], Cycles[{{1, 3}}]}

We could do

VertexReplace[g, Thread[VertexList[g] -> Permute[VertexList[g], #]]] & /@ perms

or, keeping in mind that these re-labellings are isomorphic, simply use

IGReorderVertices[Permute[VertexList[g], #], g] & /@ perms
POSTED BY: Szabolcs Horvát

Thanks Szabolcs,

That is very useful. Concerning IGReorderVertices, would it then retrieve a relabelled isomorphic graph or a random labelling? If isomorphic, does it retrieve the same every time is called? is there any way to keep generating isomorphic relabellings with that or any other function or how would you extract them from the generating vector retrieved by GraphAutomorphismGroup[graph]? Thanks again.

POSTED BY: Hector Zenil

Hello Hector,

I originally started the IGraph/M package as a Mathematica interface to igraph, but since then it has gained several of these "little pieces" of code, which are often unrelated to igraph, and make it easier to work with graphs/networks in Mathematica.

In practice, these implementations of even trivial functions often end up being not so little due to the need to make them work fast and make them work on all sorts of graphs. The package is open source, so you can take a look at how things are done.

As for converting to undirected graphs, there's IGUndirectedGraph, which has three conversion modes: "Simple" does the same thing as the built-in UndirectedGraph: it uses a single undirected edge to connect vertices which have a directed edge between them. "All" creates an undirected edge for each directed one, and thus may create a multigraph. "Reciprocal" creates an undirected edge only when there are directed connections going both ways.

However, neither the built-in UndirectedGraph, not IGUndirectedGraph will preserve graph properties such as edge weights.

Thus there's IGWeightedUndirectedGraph, which preserves edge weights only (no other properties) and uses the specified function to combine weights of reciprocal edges (e.g. add them up).

As for permuting vertices, there's IGReorderVertices. It will preserve all graph properties.

To count automorphisms, you can use built-in functions: GroupOrder@GraphAutomorphismGroup[graph]. But IGraph/M also exposes the functionality of the Bliss library through IGBlissAutomorphismCount and other functions. I updated the Bliss library included in igraph to the latest version while working on this. For hard problems, Bliss will be much faster than Mathematica's built-ins. IGraph/M also has other isomorphism-related functionality that is not currently in Mathematica, such as finding subgraphs or considering edge and vertex colours.

IGraph/M is still under development, and contributions are very welcome. Such "little pieces of code" that are useful in everyday graph theory or network science work are one of the things I am looking for.

POSTED BY: Szabolcs Horvát
What about some simple code to calculate graph spectra:
Spectrum[adjmatrix_, firstkeigenvalues_: 0] :=
If[firstkeigenvalues == 0, Eigenvalues[AdjacencyMatrix[adjmatrix]],
  Eigenvalues[AdjacencyMatrix[adjmatrix], firstkeigenvalues]]
Specially because it seems the Combinatorica alternative has some issues in M- 9.

And now we can do the classical example of cospectral graphs:
Spectrum /@ {g1 = VertexAdd[GraphData[{"Cycle", 4}], 5],
  g2 = GraphData[{"Star", 5}]}
And do all sort of fancy things with GraphData that has a couple of spectra related properties.
POSTED BY: Hector Zenil
Posted 11 years ago
Good catch! I've removed that one.
POSTED BY: Michael Hale
Yes, good catch, the ToUndirectedGraph must have been something written pre Mathematica 8 when the built-in function was introduced. Nice to hear the proposal found some echo from others.
POSTED BY: Hector Zenil
Posted 11 years ago
Cool!
Is there any reason not to use built-in UndirectedGraph function for converting directed graphs to undirected graph?
POSTED BY: Jaebum Jung
Posted 11 years ago
Great! I used these functions to start the Graph, Undirected graph, and Planar graph packages on Wikicode. This discussion is listed as a reference to find improvements and expansions. How to incorporate open-source external libraries is still open to discussion. Other packages import data from external sources, so including initialization code to load an external package as part of a Wikicode package seems reasonable to me.
POSTED BY: Michael Hale
Reply to this discussion
Community posts can be styled and formatted using the Markdown syntax.
Reply Preview
Attachments
Remove
or Discard

Group Abstract Group Abstract