Group Abstract Group Abstract

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
Sort By:
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
Jaebum Jung
Jaebum Jung, Wolfram
Posted 13 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

That is useful to know about IGReorderVertices, thanks.
POSTED BY: Hector Zenil
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
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
Michael Hale
Michael Hale
Posted 13 years ago
Good catch! I've removed that one.
POSTED BY: Michael Hale
Michael Hale
Michael Hale
Posted 13 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.
Tag limit exceeded
Note: Only the first five people you tag will receive an email notification; the other tagged names will appear as links to their profiles.
Reply Preview
Attachments
Remove
or Discard