Quote: Original post by ToohrVyk
Wait, is your graph a tree ?

Indeed. travikk, your proposed XML format doesn't look like it makes any sense. Consider a very simple graph: three nodes connected in a triangle. How would you represent that with the structure you proposed? Unless your format means something very different from what it looks like it means, it can't.

Ideas:

1 - Adjacency lists. In XML, this might be,

<nodeList>   <node name="some name" id="1">       <neighbor id="10"></neighbor>       <neighbor id="5"></neighbor>       <neighbor id="7"></neighbor>   </node>   <node name="some name" id="2">       <neighbor id="3"></neighbor>   </node></nodeList>

(Disclaimer: XML is not my forte. I can see its use, but it smells of buzzwords to me.)

2 - Adjacency matrix. It's a 2d array. Element i,j contains a 1 if node i is connected to element j and a 0 otherwise. Note this is a symmetric matrix, so you only need to store half of it.

3 - Edge list. You could do this in XML. Basically, you have "edge" and "node" objects; your "edge" objects know which "nodes" they connect, and your "nodes" know which "edges" connect to them.

4 - Incidence matrix. Each row corresponds to a vertex; each column corresponds to an edge. There's a 1 in i,j, if edge j connects to vertex i.

If I'd tried writing a file format to store graphs many years ago, I'd probably have ended up with something a bit like #1 (but probably not XML -- probably a simpler text format, me being lazy). Knowing what I do now, I might just dump an adjacency matrix to a file. It has the advantage of being pretty easy. Plus, if you bother to actually store it as a bitmap, it's quite efficient. Which of these is more efficient depends on how connected your graph is, which in turn determines how sparse your adjacency matrix is.

[Edited by - Emergent on March 26, 2008 8:24:10 PM]

Quote: Original post by Emergent3 - Edge list. You could do this in XML. Basically, you have "edge" and "node" objects; your "edge" objects know which "nodes" they connect, and your "nodes" know which "edges" connect to them.

I would go for something like that because I personally find it easier and less error prone.
But I'm not sure what you mean about "the nodes need to know which edges connect to them". You mean right in the XML?

In the following, edges know about nodes but nodes don't know about edges:

Quote: Original post by Splo
But I'm not sure what you mean about "the nodes need to know which edges connect to them". You mean right in the XML?

I guess it'd make more sense to compute that at load time than to store it in the XML now that you mention it. Less error-prone if you're writing these things by hand in a text-editor, for sure. I like your solution. Nice and easy to hand-edit, at the expense of only a little more code.

Me, I've been using #2 (Adjacency matices) a lot these days, since I've been writing offline simulation stuff in Matlab, and that's the natural way to handle graphs there. Plus it makes applying results from spectral graph theory very easy. (There are theorems relating to the eigenvalues of adjacency matrices.)

But if you're going to do this in XML, your way sounds best!

Quote: Do you think we're stupid ? The image represents a non-directed graph with cycles, and the XML file structure you provide represents a directed and acyclic graph (also known as a tree, hence my question). You cannot represent the image with a format like the post above, it's a mathematical impossibility.

Yes, I'm sorry about that. Image is correct, the XML format was wrong...

Quote: Erm... A 'root' is a tree-only concept. A graph (like the one in the image) only contains nodes and edges. So, what, exactly, do you call a root in your image?

Assuming, I don't have a 'root', insted i have a graph

Quote: 3 - Edge list. You could do this in XML. Basically, you have "edge" and "node" objects; your "edge" objects know which "nodes" they connect, and your "nodes" know which "edges" connect to them.

I think this way will be the best, but stioll, is BFS a good algorithm for THIS situation?
I also think, i'd use Splo's XML format.

Oh, and i guess my function will be useless, ned to recode it. Now going to school, be back in few hours. Maybe something will come up to my head.

For an overview of the problem, look at this Wikipedia page. I would probably go with Dijkstra's algorithm if there's no heuristic.

Quote:
I think this way will be the best, but stioll, is BFS a good algorithm for THIS situation?
I also think, i'd use Splo's XML format.

As a general rule, the best way to write software that deals with data structures stored in files is to,
1 - write functions which load the file into some internal representation -- lists, arrays, structures pointing at each other, or the like,
and then,
2 - write algorithms to solve the problem on your internal representation.

In this way, your algorithms are not coupled strongly to the file format you use. If you were to switch file formats, you'd simply have to write new loader code (#1), but all your algorithms (#2) would stay the same. In a sentence: Abstract away from file formats.

So you can mostly decouple the question, "What file format should I use?" and "What algorithm should I use?" They don't affect each other much.

In this case, BFS (and all the other suggestions) will work, with similar performance. They're all very closely-related algorithms. I just suggest BFS as, if all you want is the shortest path, it is the simplest choice, and it is also optimal in the sense that it expands only as many nodes as it needs to and no more.

So how could you load Splo's format into an easy-to-work-with structure? The key characteristic your internal representation should have is that you should be able to tell immediately which nodes are connected to a given node. It should be something that your internal "node" object either stores, or that you can otherwise get quickly -- preferably in O(1) time (you shouldn't have to search over and over). E.g., each node object might contain a list of pointers to its neighboring nodes.

Finally, after few hours coded the dijkstra, which works perfectly ;) I specify ID of the start, then ID of the end and I got the path ;)
Now I need few days to manage the data file, but this won't be hread, since I need to have such a form of data:

Vertexec should be just an array like (0, 1, 2, 3, 4, 5...)
And edges would be:
(
for vertex 1: ( (DESTINATION, LENGTH [in my case, always will be 1]), ... )
for vertex 2: ( (DESTINATION, LENGTH), ... )
...
)