DevX Home Today's Headlines   Articles Archive   Tip Bank   Forums

1. Senior Member
Join Date
Dec 2004
Location
San Bernardino County, California
Posts
1,468
you can use the stream formatting codes, setting the width and left-justify switches

2. Registered User
Join Date
Nov 2008
Posts
37
Thank you it works with:
Code:
`cout.width(8); cout << right << distanceMatrix[i][j] << " ";`
I would like implement a graph product / associative graph / cartesian product of graphs. I found already some introduction:
* http://en.wikipedia.org/wiki/Cartesi...duct_of_graphs
* www.zib.de/Publications/Reports/ZR-04-52.pdf on page 7
* http://infochimie.u-strasbg.fr/maste..._Schneider.pdf on page 57
* http://www.plosone.org/article/info:...one.0001926#s2

but I do not understand it. How it is possible to implement a graph product / cartesian product of graphs?
Last edited by flaxyz; 05-22-2009 at 05:35 AM.

3. Registered User
Join Date
Nov 2008
Posts
37
I found some implementation in different languages:
* python ( http://projects.byronimo.de/mayarv/b...tors.py?rev=38 )
Code:
```def cartesian_product(G,H):
""" Return the Cartesian product of G and H.

Tested only on Graph class.

"""

Prod=networkx.Graph()

for v in G:
for w in H:

H_edges=H.edges_iter()
for (w1,w2) in H_edges:
for v in G:

G_edges=G.edges_iter()
for (v1,v2) in G_edges:
for w in H:

Prod.name="Cartesian Product("+G.name+","+H.name+")"
return Prod```
* java ( http://www.math.ucsd.edu/~fan/graphd...uct/Graph.java )
Code:
```public static Graph cartesianProduct(Graph g1, Graph g2){
Graph g=new Graph();
int x,y;
for(int i=0;i<g1.getN();i++){
for(int j=0;j<g2.getN();j++){
x=(((Vertex) g1.vertices.get(i)).x
+((Vertex) g2.vertices.get(j)).x);
y=(((Vertex) g1.vertices.get(i)).y
+((Vertex) g2.vertices.get(j)).y);
}
}

for(int i=0;i<g1.getN();i++){
for(int k=0;k<g2.getE();k++){
Edge e = (Edge) g2.edges.get(k);
x=g2.vertices.indexOf(e.u);
y=g2.vertices.indexOf(e.v);
// System.out.println("x="+x+" y="+y+ "i="+i);
Edge edge=new Edge(g.getVertex(i*g2.getN()+x),
g.getVertex(i*g2.getN()+y));
edge.color=e.color;
}
}

for(int i=0;i<g2.getN();i++){
for(int k=0;k<g1.getE();k++){
Edge e = (Edge) g1.edges.get(k);
x=g1.vertices.indexOf(e.u);
y=g1.vertices.indexOf(e.v);
Edge edge=new Edge(g.getVertex(x*g2.getN()+i),
g.getVertex(y*g2.getN()+i));
edge.color=e.color;
}
}
return g;
}```
How it is possible to change it to c++ in order to suit to our graph?

4. Senior Member
Join Date
Dec 2004
Location
San Bernardino County, California
Posts
1,468
The Java code is pretty close to what you'd write for your C++ project. The only tricky transformation part for your graph is buliding the new adjacency list - the second and third procedures in this method.

5. Registered User
Join Date
Nov 2008
Posts
37
Could you help me with tricky transformation part, please?

6. Registered User
Join Date
Nov 2008
Posts
37
Maybe anyone know how looks the data structure (inheritance?) for a product graph?

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•

 FAQ Latest Articles Java .NET XML Database Enterprise