Questions about handling graphs in Mathematica, graph theory, graph visualization, GraphPlot, the built-in Graph type and the Combinatorica` package.

learn more… | top users | synonyms (2)

4
votes
1answer
428 views

(Efficiently) Generating graphs with vertex degree 3 for all vertices

I'm working on a graph theory problem, and given $n$ vertices, I would like to be able to generate all non-isomorphic connected graphs (not necessarily simple) with $n$ vertices, each having degree 3. ...
4
votes
1answer
165 views

Enhancing GraphUtilities' GraphEdit

One thing I use Mathematica for is building molecular graphs. Until now, I've been content with generating an adjacency matrix from SMILES data, and passing that to ...
4
votes
1answer
216 views
4
votes
1answer
190 views

What's the most intelligent way to store the information of a selfmade graph?

I have a very long list of element, say $a1,a2, a3$,..., and they are all connected in that each is the child of many parents. E.g. $a74$ is associated with $a2,a55,a71$, and also contains ...
4
votes
1answer
217 views

How do I find a weighted bipartite graph's minimum edge cover using Mathematica 8?

In graph theory, we use the Hungarian Algorithm to compute a weighted bipartite graph's minimum edge cover (a set of edges that is incident to every vertices, the one with the minimum total weight.) ...
4
votes
1answer
205 views

Removing edge weights from a Graph

How can I remove EdgeWeights from a Graph without affecting any other properties of the graph? Let's construct a graph with ...
4
votes
1answer
1k views

Is it possible to generate a Hasse Diagram for a defined relation?

I'm looking for a way to create a Hasse Diagram from a given partial order binary relation. The relation will be given explicitly, for example: ...
4
votes
0answers
100 views

Efficient Generation of Subgraphs (or, unfriend a friend a day)

NB: If you're not interested in the back-story, you could simply jump forward to the code which I'm seeking to optimize. Also, I believe this code would only work for MMA 8.0 and above. My friends ...
4
votes
0answers
205 views

Counting paths of a certain length between a source and sink vertex

I have a graph $G$, which may be directed or not, and I was wondering if there was an efficient way of using, say, BreadthFirstScan[] and FindShortestPath[] to count the number of paths between some ...
4
votes
0answers
318 views

Finding a Graph Shortest Path with Custom Graph Distance Function

What is the best way to find a shortest path by using a custom distance function? I'm trying to play a little bit with the concept of using distributions instead of a deterministic weight value for ...
3
votes
3answers
549 views

How to find all graph isomorphisms in FindGraphIsomorphism

I found the second definition of the function FindGraphIsomorphism not working. Here's the definition Mathematica 8 gives: ...
3
votes
3answers
149 views

Product of edge weights in path

I need to calculate the product of graph edge weights on the path taking into account edge direction. I.e. for graph ...
3
votes
3answers
704 views

How to draw a directed graph with arrows showing vertically from bottom to top

If I have a directed graph, how can I draw it with arrows pointing vertically from bottom to top, like showing a class inheritance pattern in OOP(object oriented programming)?
3
votes
1answer
923 views

How can I draw the transition diagram of a Markov chain?

I apologize for my heaviness as I am a Mathematica novice. Is there a kind soul who can tell me how to draw diagrams like those shown on page 158, 160 and 161 of this document.Chaine de Markov I ...
3
votes
2answers
138 views

The same value of VertexSize for vertices in different graphs causes different vertices size

I generated some graphs. The smallest vertices in the 1st graph should be the same size as the smallest vertices in the second graph. The smallest vertices have the same size (...
3
votes
2answers
104 views

Turning evaluation off

I am making a directed graph, but Mathematica keeps trying to evaluate my labels. I know that I can just use " ", but I have a lot of input. Is there a way to turn evaluation off? ...
3
votes
1answer
121 views

Social Network Analysis - Get the End Points of an Edge

I want to get the end points of an Edge of a Graph. For example see the following source, ...
3
votes
2answers
235 views

Combinatorica: Girth[] and FindCycle[] disagreement

Warning: run the following code in a fresh Mma session, as some symbols could be shadowed (depending on your Mma version) While trying to answer this question, I fell into the following: ...
3
votes
1answer
698 views

How to write a function to add edges or vertex to a graph

I need to add either a vertex or an edge to a graph, and also sometimes, vertices or edges, or a mixture of the two. How to write a function for this?
3
votes
2answers
93 views

CommunityGraphPlot doesn't size

When I need to plot a 'large' graph with CommunityGraphPlot the output is always sized at the Mathematica default value. The Graph object itself can be resized with ImageSize option. However that ...
3
votes
2answers
186 views

FindShortestPath with negative weights isn't working

I have the following functions defined: ...
3
votes
2answers
145 views

Manually adjust graph vertex location by dragging?

Sometimes I have a graph and I want to make tweaks to the vertex locations. Is there any way to manually adjust graph vertex location by dragging? If I double click to edit, I can move around the ...
3
votes
3answers
228 views

Generating a graph where vertices correspond to points in an integer lattice and edges connect points less than a threshold distance apart

I'd like to automatically generate a graph where vertices correspond to (and have the coordinates of) points in an $A \times B$ integer lattice, and a graph is generated by connected vertices within a ...
3
votes
1answer
151 views

Vertex Labeling Problem in a Graph

I am using following codes to create a graph. ...
3
votes
1answer
333 views

Adjacency List representation of a graph

I am looking to draw a graph knowing a simple adjacency representation of the graph like: A = {{1, 3}, {2, 3}, {3, 4, 5}, {4, 5}, {5}} Where ...
3
votes
1answer
118 views

How to get VertexDelete to work?

I'm using Mathematica 9 and want to delete a single vertex and all associated edges on a graph but can't seem to get the function VertexDelete function to work. My code is below. I declare a graph ...
3
votes
2answers
161 views

How to apply GraphLayout to parts of a graph?

I'm trying to sketch polymers. Here is how I do it for the monomer: ...
3
votes
1answer
90 views

Is there really a bug in the following code, taken from the reference documentation for PetersenGraph?

PetersenGraph[5, 2, EdgeLabels -> {8 \[UndirectedEdge] 9 -> "hello"}] appears to evaluate perfectly, as expected, but in my version 9.0.1.0, the option ...
3
votes
2answers
221 views

Deleting a row or column of an adjacency matrix while maintaining the associated label

I am currently working with a weighted adjacency matrix for a directed graph, and it contains several 0 columns and rows. With the unaltered matrix, I am able to monitor the relations between vertices ...
3
votes
2answers
197 views

TreePlot EdgeLabeling Style

I am trying to control the style for edge labels in treeplot and have run into a problem. Consider these two graphs: ...
3
votes
2answers
205 views

Showing a forest with root of the trees on the top

I have a Graph object that contains a forest with directed trees. I want to draw the forest such that the root of the trees are on the top and the leaves are on the bottom. If I use the following line ...
3
votes
1answer
307 views

Combinatorica Graph from Edge List

Can someone provide an example of a Combinatorica-based graph which uses ShowGraph and Graph and takes in an explicitly defined list of edges (not some auto-generated graph). I have not been able to ...
3
votes
1answer
180 views

How do I get VertexList to work directly on older graphs defined using rules?

In MMA 8, it seems that sometimes VertexList will work with rule-based graphs without needing GraphUtilities and at other times it won't. Once it starts working, it ...
3
votes
1answer
199 views

Forcing a graph not to resize

This code: ...
3
votes
1answer
159 views

Merging Vertices of a Graph and adding up the edges weights

I have a Weighted Graph of g which looks like this. ...
3
votes
1answer
136 views

How can I highlight and individually color the connected components of a graph?

I have a graph G, and I wish to individually highlight and color the different connected components of a graph. It is simple enough to do this for one component: ...
3
votes
1answer
483 views

Combinatorica vs Built-in functions: Use of MinimumSpanningTree

What kind of argument is expected by MinimumSpanningTree (from the package Combinatorica`)? Is it possible that I am providing ...
3
votes
1answer
119 views

How do I union graph properties?

I have two graphs ...
3
votes
1answer
172 views

Labeled and Graph don't mix?

In an attempt to create a legend for a graph drawing, I find that Labeled only works without the position options (except for Center). ...
3
votes
1answer
216 views

Implementing local complements of graphs

I'm trying to write a routine which generates the local complement of a graph at a vertex. For those who don't know, the local complement for a singly-connected, undirected graph is defined as the ...
3
votes
1answer
46 views

Problems with PropertyValue when Graph's vertices are Lists

I create a Graph which vertices are lists (points in n-dimensional space) ...
3
votes
1answer
217 views

Generating a graph object where vertices are pixel coordinates and edges represent two pixels being in the same Moore neighborhood

I have a list of integer pixel positions, pts, and I wish to create one or more graph objects where vertices at these pixel positions share an edge if they are ...
3
votes
1answer
256 views

How to assign graph-node label as node value?

I am facing the following problem: I need to work on several already-designed graphs, accessible in ".DOT" format. Mathematica can perfectly read these graphs, however because the nodes of the graphs ...
3
votes
1answer
96 views

LineGraph Labels

I have a graph with labels on the edges: ...
3
votes
2answers
183 views

How can I construct “better” block graphs?

A graph is a block graph if it can be constructed from an undirected tree by replacing each edge with a clique. My method of generating "random" block graphs is as follows. The parameters are the ...
3
votes
1answer
370 views

Control over depth-first scan and breadth-first scan

Is there a way to conditionally take control/modify the flow during a depth-first scan or the breadth-first scan ? Say, for example, if a particular node if found, consider it as a leaf-node and ...
3
votes
0answers
130 views

A* algorithm for finding shortest path in a graph

FindShortestPath finds the shortest path between two vertices in an edge-weighted graph, allowing a choice between the Dijkstra and Bellman-Ford algorithms. In my (limited) understanding, both of ...
3
votes
1answer
121 views

Writing results directly to file

I am trying to find all simple paths in a large directed graph (542 vertex, density ~ 5%) between two nodes. For this purpose, I use the algorithm from this thread. Unfortunately, my computer is ...
3
votes
0answers
207 views

How to compute the Lovász number for the given graph in Mathematica?

Here is a graph whose adjacency matrix is ...