Graph Presentations

Everything in the world is connected by cause effect. Some connections are mutual, some are one way. Sometimes connections go in circle, sometimes cause effect has no way back. Our cognition about the world can be modeled by a knowledge web, a cluster of knowledge connected to other knowledge clusters. A single cluster have details, containing a delicate web of knowledge clusters connected by cause effect. Wise people can quickly find connections between seemly un-related knowledge, we call it bright. Efficient people can choose the best route to reach a goal with lest effort and maximum gain, we call it smart. The difference is they have spent time processed the knowledge web beforehand, so while you are searching the answer, they take no time retrieving it.

There are several graph presentations, they are the model of cause-effect knowledge web. Our model starts from a simple question: are nodes A and B related to each other? Then we introduce the direction, which differentiate the cause-effect between the two nodes. After that we introduce the concept of weight -- so that the routes from node A to B can be compared then optimized, the so called process, relaxation. Finally, we introduce the concept of feedback, the routes from node A to B don't have to be a push, it can also be a pull. After all these concept, our model is very sensitive to the structure change of the map, so that we can answer many questions such as: what is the best route from A to B, how many functional unites are in the map, what's the best route to traversal map with lest blocking, is there circle in the map, what's the speed limit from A to B...

From breadth first search (BFS) traversal the graph to index the minimum spanning tree (MST), from depth first search (DFS) traversal the graph to index the shortest path tree (SPT); from education to machine learning; from edge relaxation to meditation...these are all activities of preprocessing the knowledge web.

The best way to traversal the graph related knowledge web is to play with it. So you have some pre-knowledge as guidance, instead of taking the brutal force approach DFS and BFS. In the javascript toy below. you can modify the connection code at left, the graph on the right will change accordingly. You can copy/paste the connection code example to the code area and see how the graph changes at the right.

Digraph

code from http://viz-js.com/, dot language syntax

Graph (colored and no duplicate edges)

strict graph {
  a[color=red];f[style=filled];
  a -- c
  d -- b
  b -- a [color=blue]
  a -- d
  d -- c
  d -- a
} 

simple graph

graph {
    a -- b;
    b -- c;
    a -- c;
    d -- c;
    e -- c;
    e -- a;
}

simple digraph

digraph {
    a -> b;
    b -> c;
    c -> d;
    d -> a;
}

weighted graph

graph {
    a -- b[label="0.2",weight="0.2"];
    a -- c[label="0.4",weight="0.4"];
    c -- b[label="0.6",weight="0.6"];
    c -- e[label="0.6",weight="0.6"];
    e -- b[label="0.7",weight="0.7"];
}

weighted digraph

digraph {
    a -> b[label="0.2",weight="0.2"];
    a -> c[label="0.4",weight="0.4"];
    c -> b[label="0.6",weight="0.6"];
    c -> e[label="0.6",weight="0.6"];
    e -> e[label="0.1",weight="0.1"];
    e -> b[label="0.7",weight="0.7"];
}

highlight a path

graph {
    a -- b -- d -- c -- f[color=red,penwidth=3.0];
    b -- c;
    d -- e;
    e -- f;
    a -- d;
}

subgraph

digraph G {

subgraph cluster_0 {
style=filled;
color=lightgrey;
node [style=filled,color=white];
a0 -> a1 -> a2 -> a3;
label = "process #1";
}

subgraph cluster_1 {
node [style=filled];
b0 -> b1 -> b2 -> b3;
label = "process #2";
color=blue
}
start -> a0;
start -> b0;
a1 -> b3;
b2 -> a3;
a3 -> a0;
a3 -> end;
b3 -> end;

start [shape=Mdiamond];
end [shape=Msquare];
}

simple subgraph

digraph {
    subgraph cluster_0 {
        label="Subgraph A";
        a -> b;
        b -> c;
        c -> d;
    }

    subgraph cluster_1 {
        label="Subgraph B";
        a -> f;
        f -> c;
    }
}

graph -- adjacency-list data structure

graph {
    rankdir=LR; // Left to Right, instead of Top to Bottom
    a -- { b c d };
    b -- { c e };
    c -- { e f };
    d -- { f g };
    e -- h;
    f -- { h i j g };
    g -- k;
    h -- { o l };
    i -- { l m j };
    t -- z;
}

digraph -- adjacency list data structure

digraph {
    a -> {b, c};
    b -> {c, a};
    d -> a;
}

symbol graph

strict graph{
    "Tin Men" -- {"DeBoy", "BlumenFeld"};
    "Kevin" -- {"Animal House", "The Woodsman"};
    "Animal House" -- {"Kevin", "Donald"};
    "Donald" -- {"The Eagle Has landed","Cold Mountain"};
}

Highlight a directed cycle

digraph {
    a -> b -> d -> c -> a[color=red,penwidth=3.0];
    b -> c;
    d -> e;
    e -> f;
    a -> d;
}