# Is there software for graph product calculation and visualization?

I am interested in finding a program which can calculate and preferably also visualize various products of not huge graphs.

More specifically, I work with labeled, directed multigraphs, and would like to be able to calculate and visualize especially the lexicographic product of such graphs.

Further, as it more precisely is a close variant of the lexicographic product I am interested in, it would be preferable if modifying the predefined operation is possible.

Specifically, I am interested in the following: where L(sG) constitute the set of labels on node s in graph G, and pre(tH) is one of two sets of labels for t in H, the product is one such that 1) the set of nodes is (s,t) such that pre(tH) is a subset of L(sG), 2) (s,t) and (s',t') are related in GxH as specified by the lexicographic product, and 3) the labels L(sGxH) are [those from L(sG) plus those from the second set of labels of t in H called post(t,H)] minus [those from L(sG) inconsistent with the new post(t,H)].

I do not assume that the program in question has the specified operation pre-programmed, but it would be very nice if it was implementable with some tampering.

Does any one know of a package that would allow this?

• Your edit is better suited as a comment on @jernej's post Nov 30, 2012 at 16:37
• I don't quite follow what do you mean by "close variant". Can you describe more precisely what exactly do you want? Dec 1, 2012 at 12:31
• Of course. I have done so now. I hope this is specific enough -- further details, I'm afraid, would require auxiliary definitions. Dec 4, 2012 at 18:18
• In terms of calculating the adjacency, for most products of graphs, it simply involves Kronecker products of the original adjacencies wiki.canisiusmath.net/… Dec 6, 2012 at 18:15

I think that Sage is the right thing for this task.

Example.

sage: G = digraphs.Circuit(40)
sage: G = G.lexicographic_product(G)
sage: G.show()


Other graph products and algorithms are available as well.

try also this recent ref:

Visualization of Graph Products by Janicke et al, IEEE Transactions on Visualization and Computer Graphics (2010)

... Graph products constitute a class that arises frequently in graph theory, but for which no visualization algorithm has been proposed until now. In this paper, we present an algorithm for drawing graph products and the aesthetic criterion graph product's drawings are subject to. We show that the popular High-Dimensional Embedder approach applied to cartesian products already respects this aestetic criterion, but has disadvantages. We also present how our method is integrated as a new component into the TopoLayout framework. Our implementation is used for further research of graph products in a biological context.