java使用数据图数据对象

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

public final class Vertex {
    String label;

    public Vertex(String label) {
        this.label = label;
    }

    public String getLabel() {
        return label;
    }

    public void setLabel(String label) {
        this.label = label;
    }

    @Override
    public int hashCode() {
        int result = 17;
        if (label != null) {
            result = 31 * result + label.hashCode();
        }
        return result;
    }

    @Override
    public boolean equals(Object o) {
        return o instanceof Vertex && label == ((Vertex) o).label;
    }
}

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118

import java.util.*;
import java.util.stream.Collectors;

public class Graph {
    private Map<Vertex, List<Vertex>> adjVertices = new HashMap<>();

    public Graph() {
    }

    private void addVertex(String label) {
        adjVertices.putIfAbsent(new Vertex(label), new ArrayList<>());
    }

    private void removeVertex(String label) {
        Vertex vertex = new Vertex(label);
        adjVertices.values()
                .stream()
                .map(e -> e.remove(vertex))
                .collect(Collectors.toList());
        // todo
        adjVertices.remove(vertex);
    }

    /**
     * 添加边界 连接两点
     *
     * @param label1
     * @param label2
     */
    private void addEdge(String label1, String label2) {
        Vertex vertex1 = new Vertex(label1);
        Vertex vertex2 = new Vertex(label2);
        if (adjVertices.containsKey(vertex1) && adjVertices.containsKey(vertex2)) {
            adjVertices.get(vertex1).add(vertex2);
        }
        if (adjVertices.containsKey(vertex1) && adjVertices.containsKey(vertex2)) {
            adjVertices.get(vertex2).add(vertex1);
        }
    }

    private void removeEdge(String label1, String label2) {
        Vertex v1 = new Vertex(label1);
        Vertex v2 = new Vertex(label1);
        List<Vertex> ev1 = adjVertices.get(v1);
        List<Vertex> ev2 = adjVertices.get(v2);
        if (ev1 != null) {
            ev1.remove(v2);
        }
        if (ev2 != null) {
            ev2.remove(v1);
        }
    }

    /**
     * 深度遍历获取图节点
     *
     * @param graph
     * @param root
     * @return
     */
    static Set<String> depthFirstTraversal(Graph graph, String root) {
        Set<String> visited = new LinkedHashSet<>();
        Stack<String> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            String vertex = stack.pop();
            if (!visited.contains(vertex)) {
                visited.add(vertex);
                List<Vertex> adjVertices = graph.getAdjVertices(vertex);
                for (Vertex v : adjVertices) {
                    stack.push(v.getLabel());
                }
            }
        }
        return visited;
    }

    public Graph(Map<Vertex, List<Vertex>> adjVertices) {
        this.adjVertices = adjVertices;
    }

    public Map<Vertex, List<Vertex>> getAdjVertices() {
        return adjVertices;
    }

    private List<Vertex> getAdjVertices(String vertex) {
        return adjVertices.get(new Vertex(vertex));
    }

    public void setAdjVertices(Map<Vertex, List<Vertex>> adjVertices) {
        this.adjVertices = adjVertices;
    }

    public static void main(String... args) {
        Graph graph = new Graph();
        graph.addVertex("bob");
        graph.addVertex("alice");
        graph.addVertex("matosiki");
        graph.addVertex("kimmi");
        graph.addVertex("rob");
        graph.addVertex("maria");
        graph.addVertex("tom");
        graph.addEdge("bob", "alice");
        graph.addEdge("alice", "matosiki");
        graph.addEdge("matosiki", "kimmi");
        graph.addEdge("kimmi", "rob");
        graph.addEdge("rob", "maria");
        graph.addEdge("maria", "bob");
        graph.addEdge("bob", "tom");
        Map<Vertex, List<Vertex>> adjVertices = graph.getAdjVertices();
        Set<String> matosiki = depthFirstTraversal(graph, "matosiki");
        for (String i : matosiki) {
            System.out.println(i);
        }
    }

}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83

import org.jgrapht.Graph;
import org.jgrapht.graph.DefaultDirectedGraph;
import org.jgrapht.graph.DefaultEdge;
import org.jgrapht.graph.SimpleGraph;
import org.jgrapht.traverse.DepthFirstIterator;

import java.net.MalformedURLException;
import java.net.URL;
import java.util.Iterator;

public class HelloJGraphT {
    private HelloJGraphT() {
    }

    public static void main(String... args) throws MalformedURLException {
        Graph<String, DefaultEdge> stringGraph = createStringGraph();
        System.out.println(stringGraph.toString());

        System.out.println("======================");

        Graph<URL, DefaultEdge> hrefGraph = createHrefGraph();
        System.out.println(hrefGraph);

        URL start = hrefGraph.vertexSet().stream()
                .filter(url -> url.getHost().equals("www.jgrapht.org"))
                .findAny().get();

        System.out.println("开始探索url图");
        traverseHrefGraph(hrefGraph, start);


    }


    private static void traverseHrefGraph(Graph<URL, DefaultEdge> hrefGraph, URL start) {
        Iterator<URL> iterator = new DepthFirstIterator<>(hrefGraph, start);
        while (iterator.hasNext()) {
            URL url = iterator.next();
            System.out.println(url);
        }
    }


    private static Graph<URL, DefaultEdge> createHrefGraph() throws MalformedURLException {
        Graph<URL, DefaultEdge> g = new DefaultDirectedGraph<>(DefaultEdge.class);

        URL google = new URL("http://www.google.com");
        URL wikipedia = new URL("http://www.wikipedia.org");
        URL jgrapht = new URL("http://www.jgrapht.org");

        g.addVertex(google);
        g.addVertex(wikipedia);
        g.addVertex(jgrapht);

        g.addEdge(jgrapht, wikipedia);
        g.addEdge(google, jgrapht);
        g.addEdge(google, wikipedia);
        g.addEdge(wikipedia, google);

        return g;
    }

    private static Graph<String, DefaultEdge> createStringGraph() {
        Graph<String, DefaultEdge> g = new SimpleGraph<>(DefaultEdge.class);
        String v1 = "v1";
        String v2 = "v2";
        String v3 = "v3";
        String v4 = "v4";

        g.addVertex(v1);
        g.addVertex(v2);
        g.addVertex(v3);
        g.addVertex(v4);

        g.addEdge(v1, v2);
        g.addEdge(v2, v3);
        g.addEdge(v3, v4);
        g.addEdge(v4, v1);

        return g;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

import com.google.common.graph.Graph;
import com.google.common.graph.MutableValueGraph;
import com.google.common.graph.ValueGraphBuilder;

public class GuavaGraph {
    public static void main(String... args){
        MutableValueGraph<Object, Object> g = ValueGraphBuilder.directed().build();
        g.addNode("v1");
        g.addNode("v2");
        g.addNode("v3");
        g.addNode("v4");
        g.edgeValue("v1","v2");
        g.edgeValue("v2","v3");
        g.edgeValue("v3","v4");
        g.edgeValue("v4","v1");
        Graph<Object> graph = g.asGraph();
        graph.nodes().stream().forEach(System.out::println);
    }
}